Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-02

07:19

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
  [1,2,3] ++ [4]
= 1 : ([2,3] ++ [4])
= 1 : (2 : ([3] ++ [4]))
= 1 : (2 : (3 ++ ([] ++ [4])))
= 1 : (2 : (3 : [4]))
= 1 : (2 : [3,4])
= 1 : [2,3,4]
= [1,2,3,4]

ステップ数は、(++) の第一引数の要素数 x 2 + 1

大きなリストの最後に何かくっつける場合は影響あるかも。


(!!)                :: [a] -> Int -> a
xs     !! n | n < 0 =  error "Prelude.!!: negative index"
[]     !! _         =  error "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
  [1,2,3,4] !! 2
= [2,3,4] !! 1
= [3,4] !! 0
= 3

ステップ数は、(!!) の第二引数 + 1


(++) も (!!) も O(N) の関数。ついでに length なんかも O(N)。リスト操作系はだいたいそう。ちょっと注意が必要。


探索

10:46

いいのみつけた。

探索

深さ優先探索
dfs :: (a -> [a]) -> a -> [a]
dfs f x = x:(f x >>= dfs f)
幅優先探索
bfs :: (a -> [a]) -> a -> [a]
bfs f = bfs' . (:[])
  where bfs' [] = []
        bfs' xs = xs ++ bfs' (xs >>= f)

-- 一行で書くと
bfs f = concat . takeWhile (not.null) . iterate (>> f) . (:[])
Programming:玉手箱:その他

こっちもすごく参考になる。

「ああいうことになってしまった原因は、与えられた問題に特化したコードを書こうとする姿勢にあると思われます。」

ハイすいません。あとで、そうなってしまった diff を書き直してみよう。。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090602
 |