- 追加された行はこの色です。
- 削除された行はこの色です。
[[ネタ記録庫/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
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 (force ml) (force mr))
let replace_min t =
let rec t'_m () = rp_min (t, lazy (force (snd (t'_m())))) in
fst (t'_m())
** 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)
* ちょっと似ている話 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};
#comment
*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,)