t-y-schemeの継続についての章であるChapter 13をHaskellで書いてみる。まず13.1章。 13.1 call-with-current-continuation Example 1 (+ 1 (call/cc (lambda (k) (+ 2 (k 3))))) => 4 Continuationモナドを利用する。(+)や整数リテラルがtype classのメソッ…

mymapFoldR, mymapTrad 結城さんのhttp://www.hyuki.com/haskell/20041222145051の mymapFoldR :: (a -> b) -> [a] -> [b] mymapFoldR f = foldr ((:) . f) []は*1、 mymapFoldR f (x:xs) => f x:mymapFoldR f xsと評価されます。したがって、 mymapTrad f […

http://www.sampou.org/cgi-bin/haskell.cgi?Everyday%3a2004-12-20&l=jp おまけの方の解答がよくわからなかったので自分でやってみる。 問題 (A, X), (B, Y): 位相空間, f: A -> B, g: Y -> X とする。このとき "∀a∈A, ∀y∈Y. f(a) ∈ y ⇔ a ∈ g(y)" ⇔ "fは連…

http://www.sampou.org/cgi-bin/haskell.cgi?Everyday%3a2004-12-19&l=jpより。 TODO 実数ωとはなんだろう？ 追記(2004-12-20) このエントリを書いた後にhttp://www.sampou.org/cgi-bin/haskell.cgi?Everyday%3a2004-12-19&l=jpが更新された。特別な数ではな…

いつまで引っ張るのかという感じですが…型をrefineするcast a を id :: (a -> b) -> (a -> b) にするようなcastのこと">*1が安全だと仮定すると、このように動くものが書ける。 *FunArgPerm2> [f 1 2 3 | f <- permArgsMono 3 (\a b c -> [a, b, c :: Int])]…

型安全性のためにOcamlは多相性を(計算の起こらない)変数の束縛のみに制限しているということを知った。 Haskellでは多相性に制限はかかっていないのでIORef(リファレンス)にunsafePerformIO(副作用)の併せ技で型安全性を壊せる。 cast :: a -> b cast x = u…

今度は [a b c, a c b, ...] に \a b c -> f をmapするというとてもマクロ的な作戦。 x <- newName strで作った変数はschemeのマクロのように変数の衝突を回避するけれど、 mkName strで作った変数は文字どおりstrのままでダイナミックスコープ。 permArgs' …

Template Haskell版。型の縛りがないので、素直に相対位置で([id:yts:20041210#p1]では型をあわせるために絶対位置で変数の置換を行っている)自分自身を呼び出して再帰できる。 permArgs :: Int -> ExpQ permArgs n = [| \f -> map ($ f) $(pgen n) |] pgen …

メモ。Haskell-Cafeより。 infixr 0 -:, :- data Infix f y = f :- y x -:f:- y = x `f` y main = print $ [1,2,3] -: zipWith (+) :- [4,5,6]http://www.haskell.org/pipermail/haskell-cafe/2002-July/003215.html

お題: 関数引数のpermutationの蛇足。 *TestFunArgPerm> [f 1 2 3 | f <- permArgs' (\a b c -> [a, b, c])] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} {-# OPTIONS -fallow-overlap…

面白かった。 permArgs n f = map ($ f) $ g n g [] = [id] g xxs@(x:xs) = [r . j| r <- subs xxs, j <- g xs] subs xs = scanl (flip (.)) id xs suc n = flip: map (.) n one = [] two = suc one three = suc two four = suc three five = suc four 追記(…

上記のHypersetを試していて発見したGHCiの挙動。 *Hyperset> :t let x = singleton (Right x) in x let x = singleton (Right x) in x :: forall a. (Ord a) => Set a *Hyperset> let x = singleton (Right x) *Hyperset> :t x x :: Set Integer *Hyperset>…

toList等はポリモーフィックなリストに入れて返さないといけませんね。いろいろ書かなくてはいけなくなるので少なくとも結構面倒になりそうなので、する価値がないかもしれないと思います。こんなものをイメージしていました。 data List u = forall uos. Ur…

解答(修正版) a. "!!!!!!!;6'uVO%_e" b. "!\"#$%&'fosI;t`Hg" c. "\"%'[03569FfLoUXy" 追記 ['!'..'z']ではありませんでした。ついでに書き直したもの。 import Control.Monad.Fix (fix) solveall = [solve g t characters 16 largenum | (g, t) <- [(gen_a,…

GADTを使ったAVLにFiniteMap-likeなインターフェイスをかぶせてベンチマークしてみた。かなり遅い。insとdelを対称っぽくするためにbalanceでコンストラクタのつけ外しが増えているので、多分酒井さんのもののよりも遅いでしょう。AVL.tgz(修正)*1 *1:Mainta…

関数はEqのインスタンスではないが… Haskellでは関数はEqクラスに属さない。定義域が無限集合の場合には二つの関数が等しいことを有限の手続きでは証明できないためだ。それはまあいいのだが、 f = ... g = fこういう場合でさえもfとgが等しいかどうかを判定…

型が一致しないので、Data.Dynamicを使ってみる。 import Data.Dynamic s = toDyn s' where s' :: Dynamic -> Dynamic -> Dynamic -> Dynamic s' f g x = (f # x) # (g # x) k = toDyn k' where k' :: Dynamic -> Dynamic -> Dynamic k' x y = x infixl 3 # …

s k s :: (a -> b -> c) -> a -> b -> c s k k :: a -> as f g x = f x (g x) k x y = x -- s :: (a -> b -> c) -> (a -> b) -> a -> c -- k :: a -> b -> a -- s: c == a -- s k :: (a -> b) -> a -> a -- s k: a == (a -> b -> c), b == ((a -> b) -> a ->…

長さをタイプチェックできるリストが欲しかったので、 infixr 5 :*: data FixedList b a = a :*: b a -- deriving Show -- 要るかな？ data Nul a = Nul deriving (Show, Eq) instance Functor Nul where fmap _ _ = Nul instance Functor b => Functor (Fix…

hypersetって何？なレベルなのだけど。;-)Set uかuかによってアルゴリズムが違うのでタイプクラスを使わないとできなさそう。 マルチパラメータタイプクラスを使わずにできるだろうか？ 問題 f :: k -> A a -> B k として型 a または C a をとれるような関数…

ツリーの端のために領域が無駄になるという指摘は面白かった。こういう時にもViewsが役にたちそう。実現しそうにないけれど、個人的には非常に欲しい機能だ。 真似して data ViewOfT = VT (VT a) a (VT a) | VE toView (N a) = VT a E E ... fromView (VT a …

きのうのmemo関数にちょっと工夫をすれば、インターフェイスもこのようになる。 fib' = memo1' (\f n -> case n of 0 -> 0 1 -> 1 _ -> f (n - 1) + f (n -2))これで一次元版は一応の完成。 memo1' f n = memo1 (\n xs -> f (\m -> shift xs n m) n) n where…

"top-downのmemoization"をしばらく前に思いついてhttp://www.sampou.org/cgi-bin/haskell.cgi?p=Programming%3a%b6%cc%bc%ea%c8%a2%3a%ca%b8%bb%fa%ce%f3&l=jp#6にも書きこんだのだが、今日は http://d.hatena.ne.jp/tanakh/20041126 に触発されてmemoizati…