Haskell - 関数プログラミング(Data.ListモジュールのgroupBy関数を(左)畳み込みを使って定義)

Real World Haskell
実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan, John Goerzen, Don Stewart(著)
山下 伸夫, 伊東 勝利
株式会社タイムインターメディア(翻訳)

開発環境

• OS X Lion - Apple(OS)
• BBEdit - Bare Bones Software, Inc.(Text Editor)
• プログラミング言語: Haskell (純粋関数型)

Real World Haskell』(Bryan O'Sullivan、John Goerzen、Don Stewart(著)、山下 伸夫、伊東 勝利、株式会社タイムインターメディア(翻訳)、オライリー・ジャパン、2009年、ISBN978-4-87311-423-3)の4章(関数プログラミング)の4.6(ループをどのように考えるか)の練習問題6.を解いてみる。

6.

入出力結果(Terminal, ghci)

$ ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :module +Data.List
Prelude Data.List> groupBy (==) [1,2,3,4,5]
[[1],[2],[3],[4],[5]]
Prelude Data.List> groupBy (==) [1,2,3,4,5,1,2,3,4,5]
[[1],[2],[3],[4],[5],[1],[2],[3],[4],[5]]
Prelude Data.List> groupBy (>) [1,2,3,4,5]
[[1],[2],[3],[4],[5]]
Prelude Data.List> groupBy (<) [1,2,3,4,5]
[[1,2,3,4,5]]
Prelude Data.List> groupBy (<) [5,1,2,3,4,5,6,7,8,9,10]
[[5],[1,2,3,4,5,6,7,8,9,10]]
Prelude Data.List> groupBy (<) [5,6,1,3,4,5,6,7,8,9,10]
[[5,6],[1,3,4,5,6,7,8,9,10]]
Prelude Data.List> groupBy (<) [5,6,1,3,4,5,6,1,2,3,4,5]
[[5,6],[1,3,4,5,6],[1,2,3,4,5]]

Data.ListモジュールのgroupByは、ghciでいろいろ試してみたところ、リストの要素を左から順に2つずつ順に与えられた関数で判定して真の場合は1つのリストにグループ化してリストを作成していき、偽の場合はその要素からまた同様に真偽を判定してグループ化して1つのリストにしていく関数っぽい。ということで、その関数を畳み込みで独自に定義してみることに。

と思ったら、隣同士の要素を条件で判定するわけではないみたい。

コード(BBEdit)

Sample.hs

-- file: Sample.hs
myGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
myGroupBy p xs = foldr step [] xs
    where step x ((y:ys):zs) | p x y = (x:y:ys):zs
                             | otherwise = (x:[]):((y:ys):zs)
          step x [] = (x:[]):[]

a = [1,2,3,4,5,1,2,3,4,5]
b = [5,4,3,2,1,5,4,3,2,1]
c = []
d = [1]
e = [1,1,2,3,4,5,5,4,3,2]

入出力結果(Terminal, ghci)

*Main Data.List> groupBy (<) a
[[1,2,3,4,5],[1,2,3,4,5]]
*Main Data.List> myGroupBy (<) a
[[1,2,3,4,5],[1,2,3,4,5]]
*Main Data.List> groupBy (<) b
[[5],[4],[3],[2],[1,5,4,3,2],[1]]
*Main Data.List> myGroupBy (<) b
[[5],[4],[3],[2],[1,5],[4],[3],[2],[1]]

まず要素を1つ取って、次の要素から順に最初に取った要素と与えられた条件で判定していき、真の間はそれらをグループ化してリストにし、偽になったらその偽になった要素からまた同じ事を繰り返していくみたい。ということで書き直し。右畳み込み(foldr)を使おうと考えてみたもののよく分からなかったので左畳み込み(foldl)を使う事を考えてみる事に。

コード(BBEdit)

Sample.hs

-- file: Sample.hs
myGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
myGroupBy p xs = foldl step [] xs
    where step ys x | null ys = (x:[]):ys
                    | p (head (last ys)) x = (init ys) ++ (((last ys) ++ (x:[])):[])
                    | otherwise = ys ++ ((x:[]):[])

a = [1,2,3,4,5,1,2,3,4,5]
b = [5,4,3,2,1,5,4,3,2,1]
c = []
d = [1]
e = [1,1,2,3,4,5,5,4,3,2]

入出力結果(Terminal, ghci)

*Main Data.List> :load Sample.hs
[1 of 1] Compiling Main             ( Sample.hs, interpreted )
Ok, modules loaded: Main.
*Main Data.List> groupBy (<) a
[[1,2,3,4,5],[1,2,3,4,5]]
*Main Data.List> myGroupBy (<) a
[[1,2,3,4,5],[1,2,3,4,5]]
*Main Data.List> groupBy (<) b
[[5],[4],[3],[2],[1,5,4,3,2],[1]]
*Main Data.List> myGroupBy (<) b
[[5],[4],[3],[2],[1,5,4,3,2],[1]]
*Main Data.List> groupBy (<) c
[]
*Main Data.List> myGroupBy (<) c
[]
*Main Data.List> groupBy (<) d
[[1]]
*Main Data.List> groupBy (<) e
[[1],[1,2,3,4,5,5,4,3,2]]
*Main Data.List> myGroupBy (<) e
[[1],[1,2,3,4,5,5,4,3,2]]

使ったのは右畳み込み(foldr)じゃなくて左畳み込み(foldl)だけど、groupByと結果が同じだし、とりあえずこれでいいのかな。。