ネタ記録庫/Haskell の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• ネタ記録庫/Haskell へ行く。
• ネタ記録庫/Haskell の差分を削除

[[ネタ記録庫/Haskell]]
#contents
* totally insane? 純粋関数的に1パスで木の全てのノードを最小値に書き換える [#m8ae406f]
http://obfuscatedcode.wordpress.com/2008/02/16/functional-pearl-trees/
 data Tree a = Leaf a          -- The leaf holds data of any type.
             | Branch (Tree a) (Tree a) deriving (Show)
 
 
 replaceMin :: Tree Int -> Tree Int
 replaceMin t = let (t', m) = rpMin (t, m) in t'
 
 rpMin :: (Tree Int, Int) -> (Tree Int, Int)
 rpMin (Leaf a, m) = (Leaf m, a)
 rpMin (Branch l r, m) = let (l', ml) = rpMin (l, m)
                             (r', mr) = rpMin (r, m)
                    in (Branch l' r', ml `min` mr)
** OCaml版 [#t523287d]
 open Lazy
 let ( !$ ) = force
 
 type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
 let rec rp_min = function
   | Leaf a, m -> Leaf m, a
   | Branch (l,r), m ->
       let l', ml = rp_min (l, m) in
       let r', mr = rp_min (r, m) in
       Branch (l', r'), lazy (min !$ml !$mr)
 
 let replace_min t =
   let rec t'_m _ = rp_min (t, lazy !$(snd (t'_m ()))) in
   fst (t'_m ())
- この場合 t'_m が 2回走るため 実質 2パス

** OCaml版 (変数への代入を使う方法) [#xd5eed1f]
 type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
 let rec map f = function
   | Leaf l -> Leaf (f l)
   | Branch (l, r) -> Branch (map f l, map f r)
 
 let replace_min t =
   let m = ref 0 in
   map (fun a -> m := min !a !m; m) t
- この場合 replace_min : int ref tree -> int ref tree になってしまう…

** OCaml版 その3 (変数への代入と遅延評価を使う方法) [#qbfe1e58]
 type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree;;
 let rec rp_min : (int tree * int ref) -> (int tree t * int) = function
   | Leaf a, m -> (lazy (Leaf !m)), a
   | Branch (l,r), m ->
       let l', ml = rp_min (l, m) in
       let r', mr= rp_min (r, m) in
       lazy (Branch (!$l', !$r')), min ml mr;;
 
 let replace_min t : int tree =
   let cell = ref 0 in
   let t', m = rp_min (t,cell) in
   cell := m; !$t'
- これで replace_min : int tree -> int tree になった！ がこれは1パスではないような気も

** OCaml版 その4 (高階関数を使う方法) [#x09966c1]
 type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
 
 let rec repMin t =
     match t with
     | Leaf    a  -> ((fun m -> Leaf m), a)
     | Branch (l,r) -> 
       let (lf, lm) = repMin l in
       let (rf, rm) = repMin r in
       	  ((fun m -> Branch (lf m,rf m)), min lm rm)
 let replace_min t =
     let (f,m) = repMin t in 
     	f m 
- Haskellの遅延評価をエミュレート？その3の純粋関数型バージョン

** F#版？ [#h8daf3df]
 #light
 type tree<'T> = Leaf of 'T | Branch of tree<'T> * tree<'T>  
      with override t.ToString() = 
        match t with
              |Leaf v
               ->sprintf "(Leaf %A)" v
              |Branch (lhs,rhs)
               -> sprintf "(Branch %s %s)" (lhs.ToString()) (rhs.ToString())
    
 let rec rp_min = 
     function Leaf a, m -> Leaf m, a
            |Branch (l,r), m
                -> let l', ml = rp_min (l, m)
                   let r', mr = rp_min (r, m)
                   Branch (l', r'), lazy (min (ml.Force()) (mr.Force()))
    
 let replace_min t = let rec t'_m () = rp_min (t, lazy ((snd (t'_m ())).Force()))
                     fst (t'_m ())

 let rec force_nodes  =
     function Leaf (lv: Lazy<'T>)
                 -> (Leaf(lv.Force()))
            |Branch (lhs,rhs)
                 -> Branch( (force_nodes lhs), (force_nodes rhs))
    
 let tree_before = Branch(Branch(Leaf(lazy 2), Branch(Leaf(lazy 1), Branch(Leaf(lazy 3), Leaf(lazy 5)))), Leaf(lazy 4))
 let tree_after = replace_min( tree_before )
 printfn "Before: %O" (force_nodes tree_before)
 printfn "After : %O" (force_nodes tree_after)
** 参考 [#t96787d1]
- http://d.hatena.ne.jp/syd_syd/20081122 のコメント欄

* ちょっと似ている話 breadth-first numbering by Chris Okasaki [#iccbd9bf]
- http://okasaki.blogspot.com/2008/07/breadth-first-numbering-algorithm-in.html
- http://www.scribd.com/doc/2913491/BreadthFirst-Numbering
- http://portal.acm.org/citation.cfm?id=351253

* StateT [#x763ddb2]
これは、permutationを返す関数：
 permutation' :: [[Int]] -> Int -> [Int] -> [[Int]]
 permutation' result 0 _ = result
 permutation' result n cand =
     do a <- cand
        permutation' (map (a:) result) (n-1) [x|x<-cand,x/=a]

使い方
 permutation' [[]] [1,2,3] 2
のように使う。

これをStateTを使ってわざと分かりにくくしてみる：

 permutation :: [[Int]] -> Int -> StateT [Int] [] [[Int]]
 permutation result 0 = return result
 permutation result n =
     do cand <- get
        a <- lift cand
        put [x|x<-cand,x/=a]
        permutation (map (a:) result) (n-1) 

これは
 runStateT (permutation [[]] 2) [1,2,3]

のように使う。
- Thx. 勉強になります。 -- [[げんま]] &new{2007-04-24 (火) 12:45:05};
- 使い方は、permutation' [[]] 2 [1,2,3]  ではないでしょうか? <-元職業プログラマ --  &new{2008-07-10 (木) 22:46:11};

*HaskellでWIKI [#x4eef27a]
書いてみました。いまのところ日本語は使えません。
http://icecs.ice.nuie.nagoya-u.ac.jp/~h043078b/wiki.cgi

* History of Haskell [#z4d010cb]
- http://haskell.org/haskellwiki/History_of_Haskell
- HOPL'07に提出する予定の論文の、ドラフトだそうです。

* HaskellでOS。 [#s0a682d7]
http://www.cse.ogi.edu/~hallgren/House/ -- [[源馬]] &new{2006-07-04 (火) 16:16:05};

*The Evolution of a Haskell Programmer [#ga1c48ba]
[[The Evolution of a Haskell Programmer:http://www.willamette.edu/~fruehr/haskell/evolution.html]] かなりハイレベルにバカやってる感じ
- バカだ〜！fold関数使うまではわかるけど、その後が！まだまだまだまだ続くし。 -- [[げんま]] &new{2006-08-12 (土) 10:35:43};
- インタプリタを作って階乗計算させたり，型クラスを使ったテクニックなんかもあるので分かると結構良いかも。 -- [[けいご]] &new{2006-08-12 (土) 15:27:52};

* Haskell 型クラス、MPTC, Fundeps と type improvement by けいご [#r0d7ac1a]
- 2008/10/22
#ref(活動記録/20081022/fundeps.pdf,)