haskellグループ化機能も同様にできますか？

Question

は何とかしたものと同様に、グループ機能を作成することが可能です：

group[1,2,2,3,3,3,4,1,1] ==> [[1],[2,2],[3,3,3],[4],[1,1]] 

PS：

group :: [Int] -> [[Int]] 
group [] = [] 
group (x:[]) = [[x]] 
group (x:y:ys) 
    | x == y = [[x,y], ys] 
    | otherwise = [[x],[y], ys] 

結果はそのようなものにshoult「私はすでにData.Listの実装を探したが、それはdoesnの私を助けてください。 （https://hackage.haskell.org/package/base-4.3.1.0/docs/src/Data-List.html）

Data.Listの実装よりもグループの機能をより明確にすることは可能ですか？

誰かが簡単にData.Listの実装について簡単に説明できますか？

Answer 1

あなたのアイデアは良いですが、私は、蓄積されたグループを保存するために補助的な機能（以下group_loopのようなもの）を定義する必要があると思います。 （同様のデバイスは、DataListの実装で使用されるspanを定義するために必要です;あなたが望むように直接groupを定義するのは複雑ではありません。）あなたは、基本的には限りが一致するようサブグループに項目を追加し、元のリストに沿って移動することを計画したが、何かが一致しない場合は、新しいサブグループを始めている。

group [] = [] 
group (x:xs) = group_loop [x] x xs 
    where 
    group_loop acc c [] = [acc] 
    group_loop acc c (y:ys) 
    | y == c = group_loop (acC++ [y]) c ys 
    | otherwise = acc : group_loop [y] y ys 

サブグループを蓄積する方がよいかもしれません新しい要素を付加して、すべてを一度に反転させることによって：

group [] = [] 
group (x:xs) = group_loop [x] x xs 
    where 
    group_loop acc c [] = [reverse acc] 
    group_loop acc c (y:ys) 
    | y == c = group_loop (y:acc) c ys 
    | otherwise = reverse acc : group_loop [y] y ys 

それ以来、あなたは終わりに物事をタックするために蓄積されたサブグループをretraversing維持する必要はありません。いずれかの方法で、私は

>>> group[1,2,2,3,3,3,4,1,1] 
[[1],[2,2],[3,3,3],[4],[1,1]] 

Answer 2

groupData.Listは、groupByの特殊バージョンであり、等価演算子==を要素をグループ化する関数として使用します。

groupBy関数が次のように定義される：

groupBy     :: (a -> a -> Bool) -> [a] -> [[a]] 
groupBy _ []   = [] 
groupBy eq (x:xs)  = (x:ys) : groupBy eq zs 
          where (ys,zs) = span (eq x) xs 

それはリストの各要素に適用される機能に基づいて、2つのリストのタプルにリストを分割する別の関数呼び出しspanに依存しています。 documentation for spanには、その有用性を理解するのに役立つこのメモが含まれています。

span p xs(takeWhile p xs, dropWhile p xs)

と同等ですが、あなたが最初にspanを理解していることを確認します。 REPLでそれを少しでも遊んでください。

[OK]を今すぐgroupByに戻します。あなたが渡す比較関数を使用してspanを使用してリストを分割します。その関数はeqで、group関数の場合は==です。この場合、span関数は、リストを2つのリストに分割します。最初のものはリストから引っ張られた最初の要素に、残りはタプルの2番目の要素にマッチします。

groupByは再帰的に自分自身を呼び出すため、末尾に達するまでspanの残りの結果を追加します。あなたはこのような何かを探してspanによって生成された値と考えることができます

視覚、：

([1], [2,2,3,3,3,4,1,1]) 
([2,2], [3,3,3,4,1,1]) 
([3,3,3], [4,1,1]) 
([4], [1,1]) 
([1,1], []) 

再帰的な部分はあなたに

の結果を与え、別のリストで一緒にこれらのリストのすべての最初の要素を結合し

[[1],[2,2],[3,3,3],[4],[1,1]] 

Answer 3

を取得し、この見てのもう一つの方法は、最初の要素の入力のxと再帰的にグループそれの残りの部分を取ることです。 xはグループ化の最初の要素の前に付加されるか、新しい単独のグループに入ります。いくつかの例：[1,2,3]で

1. 、我々は[1,1,2]で[[1], [2], [3]]
2. を得、[[2], [3]]に新しいグループに1を追加します、我々は[[1,1], [2]]を得[[1], [2]]の最初のグループに最初の1を追加します。

得コード：

group :: [Int] -> [[Int]] 
group [] = [] 
group [x] = [[x]] 
group (x:y:ys) = let (first:rest) = group (y:ys) 
       in if x /= y 
        then [x]:first:rest -- Example 1 above 
        else (x:first):rest -- Example 2 above 

をIMO、これは明示的シングルトンリストを処理することによって大幅に再帰的なケースを簡単にします。