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)
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 ())
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
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'
#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)
これは、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]
のように使う。
書いてみました。いまのところ日本語は使えません。 http://icecs.ice.nuie.nagoya-u.ac.jp/~h043078b/wiki.cgi
http://www.cse.ogi.edu/~hallgren/House/ -- 源馬? 2006-07-04 (火) 16:16:05
The Evolution of a Haskell Programmer かなりハイレベルにバカやってる感じ