Pyon's Diary


舊 令和貳年庚子睦月拾陸日 (日・晴)

再歸を疊み込みに

すごい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

晩御飯

  • 海鮮ピラフ (自家製ベーコン入り)
  • 南瓜のポタージュ
comments powered by Disqus