ネタ記録庫/Haskell

totally insane? 純粋関数的に1パスで木の全てのノードを最小値に書き換える †

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版 †

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版 (変数への代入を使う方法) †

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 (変数への代入と遅延評価を使う方法) †

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#版？ †

#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)
↑

参考 &dagger;

↑

ちょっと似ている話 breadth-first numbering by Chris Okasaki &dagger;

↑

StateT &dagger;

これは、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]

のように使う。


↑

HaskellでWIKI &dagger;

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

↑

History of Haskell &dagger;

↑

HaskellでOS。 &dagger;

http://www.cse.ogi.edu/~hallgren/House/ -- 源馬? 2006-07-04 (火) 16:16:05

↑

The Evolution of a Haskell Programmer &dagger;

The Evolution of a Haskell Programmer かなりハイレベルにバカやってる感じ

  • バカだ〜！fold関数使うまではわかるけど、その後が！まだまだまだまだ続くし。 -- げんま? 2006-08-12 (土) 10:35:43
  • インタプリタを作って階乗計算させたり，型クラスを使ったテクニックなんかもあるので分かると結構良いかも。 -- けいご? 2006-08-12 (土) 15:27:52
↑

Haskell 型クラス、MPTC, Fundeps と type improvement by けいご &dagger;

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS