再帰的置換関数は常に空のリストを返します

Question

私はHaskellを学んでいます。私の練習関数の1つは単純な再帰的permuteでした。私はthe solution described hereを適応し、もともとこれを得た：

selections [] = [] 
selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ] 

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

（はい、これは短いかもしれないが、私は明示して明確にするため行っていた。）

しかし、permuteのこのバージョンは、常に空のリストを返して！

permute [] = [[]] 
permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

は、しかし、私はまだ元のバージョンは常に空のリストを返す理由へと困惑しています：少し暴れるした後、私はそれがpermuteを変更することで動作するようになりました。

Answer 1

この2つは明らかに非常によく似ています。だから、どこが不一致かを詳しく見てみませんか？再帰部分は両者でまったく同じなので、最初に両方のバージョンが空でないリストのと同じものをと言うことができます。これは異なる結果をもたらすので間違っていると思われますが、実際にはは再帰呼び出しの結果に対して同じ操作を実行します。

正しいバージョンのベースケースは、わかりやすいpermute [] = [[]]です。しかし、最初のバージョンからの基本ケースは、リストの理解に暗黙のうちである。与えられた定義は：

permute [] = [y:ps | (y,ys) <- [], ps <- permute ys] 

：定義selections [] = []考える

permute [] = [y:ps | (y,ys) <- selections [], ps <- permute ys] 

は、我々はに簡素化することができます：

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

...我々は何が起こるか見るためにxsため[]に置き換えることができます...結果が生成されないことが明らかであるので、リスト全体の理解度は空であり、単純化すると簡略化されます。

permute [] = [] 

さて、引数として[x]を代入し、ベース前の最後の再帰的ステップを考えてみます。

permute [x] = [y:ps | (y,ys) <- selections [x], ps <- permute ys] 

selectionsの定義は[x]に置き換えることselections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ]を与え、selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ]です。 selections []は[]と評価されるため、リスト全体の理解度は[]に減少し、selections [x] = (x, []) : []またはちょうどselections [x] = [(x, [])]となります。

permute [x] = [y:ps | (y,ys) <- [(x, [])], ps <- permute ys] 

あり、リスト内の唯一の要素ですので、我々は結合し、直接代替<-理解を無視することができます：

permute [x] = [y:ps | (y,ys) = (x, []), ps <- permute ys] 

permute [x] = [ x:ps | ps <- permute []] 

permute []評価することが確立された上記のようpermuteにすることを

は

代替[]に変更すると、それを同様に置き換えて、リストの理解度が再び[]に減少することがわかります。

permute [x] = [] 

...任意の入力に対して[]を返すように簡単に一般化します。 psが束縛されているので

permute [x] = [ x:ps | ps <- permute []] 

permute [x] = [ x:ps | ps <- [[]] ] 

：最終の再帰的ステップの最終還元、これは以下に置換変化を

permute [] = [[]] 

：バージョン作業は、しかし、次の定義を使用します単一の要素を持つものには、直接代用することができます。

permute [x] = (x:[]) 

permute [x] = [x]と言っています。