[[ネタ記録庫/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パスではないような気も ** 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}; - <a href="http://forum.indya.com/member.php?u=135243">EMILY 18 PUSSY</a> [url=http://forum.indya.com/member.php?u=135243]EMILY 18 PUSSY[/url] http://forum.indya.com/member.php?u=135243 EMILY 18 PUSSY <a href="http://forum.indya.com/member.php?u=135247">16 18 NUDIST TEENS</a> [url=http://forum.indya.com/member.php?u=135247]16 18 NUDIST TEENS[/url] http://forum.indya.com/member.php?u=135247 16 18 NUDIST TEENS <a href="http://forum.indya.com/member.php?u=135248">POLARKREIS 18 ALLEIN ALLEIN</a> [url=http://forum.indya.com/member.php?u=135248]POLARKREIS 18 ALLEIN ALLEIN[/url] http://forum.indya.com/member.php?u=135248 POLARKREIS 18 ALLEIN ALLEIN <a href="http://forum.indya.com/member.php?u=135249">POLARKREIS 18 ALLEIN</a> [url=http://forum.indya.com/member.php?u=135249]POLARKREIS 18 ALLEIN[/url] http://forum.indya.com/member.php?u=135249 POLARKREIS 18 ALLEIN <a href="http://forum.indya.com/member.php?u=135251">18 YEAR OLD GIRLS</a> [url=http://forum.indya.com/member.php?u=135251]18 YEAR OLD GIRLS[/url] http://forum.indya.com/member.php?u=135251 18 YEAR OLD GIRLS -- [[Pole]] &new{2008-12-10 (水) 03:11:01}; - <a href= http://hymm1546.977mb.com/18-teen/18-year-old-teens-pics.html >18 year old teens pics</a> <a href= http://hymm1547.977mb.com/18-porn/hot-18-year-old-porn.html >hot 18 year-old porn</a> <a href= http://hymm1547.977mb.com/18-porn/18-but-looks-younger-porn.html >18 but looks younger porn</a> <a href= http://hymm1544.977mb.com/18-sex/18-yr-sex.html >18 yr sex</a> <a href= http://hymm1546.977mb.com/18-teen/18-teen-naked.html >18 teen naked</a> [url=http://hymm1544.977mb.com/18-sex/18-yo-busty-teen-sex.html]18 yo busty teen sex[/url] [url=http://hymm1544.977mb.com/18-sex/18-sex.html]18 sex[/url] [url=http://hymm1547.977mb.com/18-porn/free-18-year-porn.html]free 18 year porn[/url] [url=http://hymm1547.977mb.com/18-porn/barely-18-amateur-porn-blowjobs+free-videos.html]barely 18 amateur porn blowjobs+free videos[/url] [url=http://hymm1546.977mb.com/18-teen/legal-naked-teen-18-girls.html]legal naked teen 18 girls[/url] http://hymm1544.977mb.com/18-sex/18-sex-movies.html 18 sex movies http://hymm1546.977mb.com/18-teen/18-nudist-teens.html 18 nudist teens http://hymm1546.977mb.com/18-teen/18-teen-fuck-pics.html 18 teen fuck pics http://hymm1546.977mb.com/18-teen/18-teen-yr-old.html 18 teen yr old http://hymm1546.977mb.com/18-teen/hot-18-teen-ass.html hot 18 teen ass -- [[Otgru]] &new{2008-12-10 (水) 19:18:04}; - OJizJNFmmr -- [[ygjortvou]] &new{2008-12-13 (土) 06:41:10}; - <a href="http://groups.yahoo.com/group/dnpspvr625/">ALL NATURAL GIRLS</a> [url=http://groups.yahoo.com/group/dnpspvr625/]ALL NATURAL GIRLS[/url] http://groups.yahoo.com/group/dnpspvr625/ ALL NATURAL GIRLS <a href="http://tech.groups.yahoo.com/group/pmnbqqz225/">GIRLS ALL CLOTHES OFF</a> [url=http://tech.groups.yahoo.com/group/pmnbqqz225/]GIRLS ALL CLOTHES OFF[/url] http://tech.groups.yahoo.com/group/pmnbqqz225/ GIRLS ALL CLOTHES OFF <a href="http://groups.yahoo.com/group/wmllcgp691/">ALL HOT GIRLS ONLY</a> [url=http://groups.yahoo.com/group/wmllcgp691/]ALL HOT GIRLS ONLY[/url] http://groups.yahoo.com/group/wmllcgp691/ ALL HOT GIRLS ONLY <a href="http://launch.groups.yahoo.com/group/dfxjxsb553/">ALL HOT GIRLS</a> [url=http://launch.groups.yahoo.com/group/dfxjxsb553/]ALL HOT GIRLS[/url] http://launch.groups.yahoo.com/group/dfxjxsb553/ ALL HOT GIRLS <a href="http://groups.yahoo.com/group/rdnsbdf507/">GIRLS SHOWING IT ALL</a> [url=http://groups.yahoo.com/group/rdnsbdf507/]GIRLS SHOWING IT ALL[/url] http://groups.yahoo.com/group/rdnsbdf507/ GIRLS SHOWING IT ALL -- [[Wpered]] &new{2008-12-13 (土) 16:12:37}; #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,)