再歸を疊み込みに
すごいH本の6.3節に出てくる findKey の再起を使つた定義は以下の通り.
findKey :: (Eq k) => k -> [(k, v)] -> Maybe v
findKey key [] = Nothing
findKey key ((k, v):xs)
| key == k = Just v
| otherwise = findkey key xs
これを foldl() を使つて定義し直す事を考える. foldl() の定義は以下の通り.
foldl _ z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
findKey() を foldl() を使つて以下のやうに定義してみる.
findKey key xs = foldl g Nothing xs
空リストを渡したときは定義から Nothing を返す.
findKey key [] = foldl g Nothing [] = Nothing
空でないリストを渡したときを書き下してみる.
findKey key [(1,'a'),(2,'b'),(3,'c')]
= foldl g Nothing [(1,'a'),(2,'b'),(3,'c')]
= foldl g (g Nothing (1,'a')) [(2,'b'),(3,'c')]
= foldl g (g (g Nothing (1,'a')) (2,'b')] [(3,'c')]
= foldl g (g (g (g Nothing (1,'a')) (2,'b')) (3,'c')) []
= g (g (g Nothing (1,'a')) (2,'b')) (3,'c')
變數keyが1,2の時はNothing, 3の時は’c’を返す函數 g z (k, v) を考える.
g z (k, v)
| k == key = Just v
| otherwise = z
とすると key == 1 の時は,
g (g (g Nothing (1,'a')) (2,'b')) (3,'c')
= g (g (Just 'a') (2,'b')) (3,'c')
= g (Just 'a') (3,'c')
= Just 'a'
key == 2 の時は,
g (g (g Nothing (1,'a')) (2,'b')) (3,'c')
= g (g Nothing (2,'b')) (3,'c')
= g (Just 'b') (3,'c')
= Just 'b'
key = 3 の時は,
g (g (g Nothing (1,'a')) (2,'b')) (3,'c')
= g (g Nothing (2,'b')) (3,'c')
= g (g Nothing (2,'b')) (3,'c')
= g Nothing (3,'c')
= Just 'c'
となつて求める結果を返す事が確認できる. 從つて findKey() は foldl() を使つて以下のやうに定義できる.
findKey key xs = fold g Nothing xs
where
g z (k, v)
| k == key = Just v
| otherwise = z
晩御飯
- 海鮮ピラフ (自家製ベーコン入り)
- 南瓜のポタージュ