[Elm]foldr(とfoldl)を勉強してループなしでも再帰で頑張る

関数型ではどうしたらいいんだろう?

elmを使ってきて多くのことはmapやfilterなどでなんとかなるのですが、ループで配列やリストを処理するとき手続き型ならこう書けるのにという場面に出くわしました。

foldlは何度か利用したことがあるのですが、foldrはありませんでした。おそらく自分のしたいことはfoldrの利用か、自前のfoldrのようなものになると思いました。

foldl

foldl

myFoldl : (a -> b -> b) -> b -> List a -> b
myFoldl func acc list =
    case list of
        [] ->
            acc

        x :: xs ->
            myFoldl func (func x acc) xs

accとはaccumulateの略のようで、意味は「蓄積する」です。

> myFoldl (::) [] [1,2,3]
1 :: []     => [1]
2 :: [1]    => [2, 1]
3 :: [2, 1] => [3, 2, 1]
[3,2,1] : List number

> myFoldl (\n str -> str ++ String.fromInt n) "" [1,2,3]
"123" : String
> S.myFoldl (\n str -> (String.fromInt n) ++ str) "" [1,2,3]
"321" : String

リスト左の要素からaccに蓄積されていき、最後にaccが結果としてreturnされるイメージです。

(::)は

> 1 :: [2]
[1,2] : List number

こういった関数です。

foldr

myFoldr : (a -> b -> b) -> b -> List a -> b
myFoldr func ini list =
    case list of
        [] ->
            ini

        x :: xs ->
            func x (myFoldr func ini xs)

x :: xsのxsとはxの複数形らしいです。
型がList Itemならば、case list,item :: itemsなどでもよさそうです。

> myFoldr (::) [] [1,2,3]
((::) 1 ((::) 2 ((::) 3 [])))
1 :: (2 :: (3 :: []))
[1,2,3] : List number

> myFoldr (\n str -> str ++ String.fromInt n) "" [1,2,3]
"321" : String
> myFoldr (\n str -> (String.fromInt n) ++ str) "" [1,2,3]
"123" : String

((::) 1 ((::) 2 ((::) 3 [])))
1 :: (2 :: (3 :: []))
渡す関数が(::)以外であれば、(::)がそれに置き換わるイメージみたいです。

汎用的でないfoldrを自分で作ってみると理解しやすいかもしれません。

foldrっぽい処理1

myFoldr2 : List Int -> List Int
myFoldr2 list =
    case list of
        [] ->
            []

        x1 :: x2 :: xs ->
            x1 * 10 :: x2 * 100 :: myFoldr2 xs

        x :: xs ->
            x * 1000 :: myFoldr2 xs

> myFoldr2 [1, 2, 3]
[10,200,3000] : List Int

> myFoldr2 [1, 2, 3, 4]
[10,200,30,400] : List Int

最終的にリストを生成したいのなら、x :: (myFoldr xs)のようにつなげて行くことになり、イメージしやすいと思います。
上の例ではxに10をかけて(::)でつなげ、新しいリストを作っている感じです。

foldrっぽい処理2

myFoldr5 : List Int -> List Int
myFoldr5 list =
    case list of
        [] ->
            []

        x :: [] ->
            [ x * 100 ]

        x :: xs ->
            x * 10 :: myFoldr5 xs

> myFoldr5 [1]
[100] : List Int
> myFoldr5 [1, 2]
[10,200] : List Int
> myFoldr5 [1, 2, 3]
[10,20,300] : List Int

foldrっぽい処理3

myFoldr6 : Bool -> List Int -> List Int
myFoldr6 flag list =
    case list of
        [] ->
            []

        x :: xs ->
            case x of
                5 ->
                    x :: myFoldr6 True xs

                _ ->
                    case flag of
                        True ->
                            x + 5 :: myFoldr6 flag xs

                        False ->
                            x :: myFoldr6 flag xs

> myFoldr6 False [1, 2, 5, 5, 6, 7]
[1,2,5,5,11,12]

まとめ

foldlは集計のような処理に、foldrは新しいリストを作るときに使いやすそうです。

参考1
参考2