カタラン数は語る（Haskell で Catalan数的組み合わせを生成する関数）

概要

• カタラン数は，CSと関わりが深いステキな数
• カタラン数の式を観察すれば，カタラン数で表現されるような組み合わせそのものを生成できる関数が作れる
• 数学楽しい

カタラン数とは？

• Qitta には，カタラン数を語らん という良いタイトルの記事があるので，それを一度読まれるといいかもしれません．
  • Wikipedia の解説も良いです("意味付け"と表現しているところは，特定の意味付けだけが正当ではなく，むしろ固定されないのが数学なのでは？と少し思いましたが．．．)
• 上記の記事にも解説があるが，カタラン数が現れる問題として以下のような例があります
  • 括弧の対応問題
    1. Wikipedia にある様に，単にn個の括弧対応を考える問題
    2. ある二項演算を用いて，多項式を単項に変換する通り考える問題
       • 例：項数3の場合，$f(f(t_1,t_2),t_3)), \ f(t_1,f(t_2,t_3))$の2通り
  • ある売り場に並ぶ2n人の内，500円玉のみ持つ人がn人，1000円札のみ持つ人がn人で，最初売り場にお釣りがない状態からはじめ，お釣りに不足がでない用に500円の商品2n個を完売できる組みあせ数(これは，括弧の対応問題の1とほぼ同じですね）
  • yahoo知恵袋で見つけたこの問題の解説はとても分かり易いです
  • 先頭からの任意の部分列においてAの数≧Bの数 かつ Aの数=Bの数である組み合わせ総数という解説は凄く良いです
  • n個の分岐点をもつ二分木のパターン数
• これらがある共通の構造だということは，CSやっている人には直感的かもしれません(とりわけ2分木をインタフェースとして解説されることが多いかも)
• CSでも，フィボナッチ数列とコラッツの数列はよく語られるけど，カタラン数(列)はもっと知られていい気がします．．．(よく知られている事を私が知らないだけ？)

カタラン数から組み合わせ関数へ

Haskell には，組み合わせに関する基本的な関数として
permutations(list) ,subsequences(list)などがあります．

Prelude Data.List> permutations [1,2,3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

Prelude Data.List> subsequences [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

これらの組み合わせの総数はそれぞれ$|list|!$ , $2^{|list|}$ となります(高校数学)．逆を言えば，このように組み合わせ総数がもとまるならば，組み合わせを実際に生成する関数も作れるのではないでしょうか？カタラン数的問題もpermutationsや subsequencesと同じように組み合わせ生成系が欲しいです．その生成系から，
括弧の対応問題も，
1000円札500円玉問題も，
木構造に関する問題も，
本質的に同じ問題であり，1つの関数でまとめて表現でき，細かい差異はパラメータの違いでしかないことが表現できると嬉しさがあります．

permutations と subsequences は，リストさえ渡せばほしい対象がすぐに分かるのでその生成系の型はわかりやすいです．カタラン数生成系はどうすればよいでしょうか？
ポイントとしては，ある「対象列」（括弧の問題で言えば数などの項の列）があり，その要素に対して何かしらの操作や判断があるという部分がカタラン数的問題では共通であることです．

カタラン数は，以下の漸化式で表すことの出来る数列のことでした．
$C_0 = 1,\ \ C_1 = 1$
$C_{n+1} = \sum_{i=0}^{n-1}{C_i}\ {C_{n-i}}$
この式を観察すれば以下の様な事がわかります．

1. リストのある地点を基準に，リストを2つの部分リストに分解する
2. 分割したリストの２つの答えをうまく合体させる(組み合わせ数だけを求める場合は積)ことで，分割したリストを合成したより大きな解を求めている

この2.に該当する部分（操作）をパラメータとして渡すものにしてあげれば，共通の抽象的生成系が作れそうです．

コード(Haskell)

catalan :: (a -> a -> a) -> [a] -> [a]
catalan f (a:[]) = [a]
catalan f xs = let
  n = pred $ length xs
  in foldr (\x y -> let
    (i, j) = splitAt x xs
    g = catalan f
    in (f <$> (g i) <*> (g j)) ++ y) [] [n, pred n..1]

ごちゃごちゃ述べたけど，要はこれだけです．．．
コードはあまりにも単純なので，詳しくは解説しません．

実行例

• 括弧の対応問題(n個の括弧対応)

*Main>  catalan (\x y -> "(" ++ x ++ ")" ++y )  ["","","",""]
["((()))","(()())","(())()","()(())","()()()"]

• 括弧の対応問題(多項式の単項化)

*Main > catalan (\x y -> "(" ++ x ++ "," ++ y ++ ")")  ["1","2","3","4"]
["(((1,2),3),4)","((1,(2,3)),4)","((1,2),(3,4))","(1,((2,3),4))","(1,(2,(3,4)))"]

TODO：2つの括弧の対応問題で渡している無名関数の違いについて解説

• 500円玉1000円札問題

*Main > catalan (\x y -> "500 "++x++" 1000 "++y )  ["","","",""]
["500 500 500  1000  1000  1000 ","500 500  1000 500  1000  1000 ","500 500  1000  1000 500  1000 ","500  1000 500 500  1000  1000 ","500  1000 500  1000 500  1000 "]

• 木構造の問題 :TODO

発展(テンパズルを解く)

私は，括弧の対応問題をみるとテンパズルを強く連想しました．
これも絶対に類型な問題だと思います．
ただし，上のcatalanでは，演算子が1種類に固定されていました．これでは，テンパズル問題は解けないですね．．．
テンパズルを解くためには，複数の演算(子)に対して，それらを非決定的に組み合わせた場合を求められるようにならなければなりません．
まず2項演算子を非決定的に組み合わせられる用にcatalanを拡張します．実はそんなにコードは変わらないです

catalans :: [a -> a -> a] -> [a] -> [a]
catalans fs (a:[]) = [a]
catalans fs xs = let
  n = pred $ length xs
  in foldr (\x y -> let
    (i, j) = splitAt x xs
    g = catalans fs
    in (fs <*> (g i) <*> (g j)) ++ y) [] [n, pred n..1]

List Applicative の非決定計算がうまくやってくれるのが，Haskell でこの問題を完結に表現できている肝だと思います．ほんと List Applicative すき．
また，この演算子非決定計算verを用いると，元のcatalanは単にシングルトンに直せばいいだけなので，以下のようにも定義できちゃいます

catalan :: (a -> a -> a) -> [a] -> [a]
catalan f = catalans [f]

2つ並べるならば，こっちのほうが同じ処理が重複しないのでいいですね
学生時代に有限オートマトンの処理系作った際に，NFA定義して，DFAをその特殊として定義した時の気持ちを思い出します...
これで，ほとんどテンパズルは解けます．あとは，元の数式が復元できるようにしてあげる工夫と，値が10の値だけfilterする仕組みをいれます

type S a = (String,a)
gs :: [S (a -> a -> a)] ->[S a -> S a -> S a]
gs = map (\(sf,f) (sx,x) (sy,y) -> (sf ++ "(" ++ sx ++ "," ++ sy ++ ")", f x y))

catalansScan :: (Show a) => [S (a -> a-> a)] -> [a] -> [S a]
catalansScan fs xs = let
  hs = gs fs
  ys = map (\x -> (show x, x)) xs
  in catalans hs ys

catalanScan :: (Show a) => S (a -> a-> a) -> [a] -> [S a]
catalanScan f = catalansScan [f]

fillCatalan :: (Eq a, Show a)=> a -> [a] -> [S (a->a->a)]-> [String]
fillCatalan ans xs fs = let r = catalansScan fs xs
  in map fst $ filter ((== ans).snd) r

制約が強い場合

Wikipedia によると，テンパズルは制約が強い場合と弱い場合があるようです．弱い場合は，"-"の単項演算を許す場合もあるようですが，まずはそれは無しで一番制約的に厳しい数のリストが順不同の場合のテンパズルを解くコードを作ります

s10Puzzle :: [Double] -> [String]
s10Puzzle f = fillCatalan 10 f [("+",(+)),("-",(-)),("*",(*)),("/",(/))]

実行例

s10Puzzle [1,2,3,4]
["+(+(+(1.0,2.0),3.0),4.0)","+(*(*(1.0,2.0),3.0),4.0)","+(+(1.0,+(2.0,3.0)),4.0)","+(*(1.0,*(2.0,3.0)),4.0)","+(+(1.0,2.0),+(3.0,4.0))","+(1.0,+(+(2.0,3.0),4.0))","+(1.0,+(2.0,+(3.0,4.0)))","*(1.0,+(*(2.0,3.0),4.0))"]

制約が弱い場合(一般的なテンパズル)

こちらはリストの数を任意に出現させてよいことになっています．
そのため，与えられたリストの順列全てに対して制約の強い10パズルを解きます

w10Puzzle :: [Double] -> [String]
w10Puzzle f = concat . map s10Puzzle $ permutations f

実行例

かなり組み合わせ数が多いです（右にスクロールすればわかる）

*Main> w10Puzzle [1,2,3,4]
["+(+(+(1.0,2.0),3.0),4.0)","+(*(*(1.0,2.0),3.0),4.0)","+(+(1.0,+(2.0,3.0)),4.0)","+(*(1.0,*(2.0,3.0)),4.0)","+(+(1.0,2.0),+(3.0,4.0))","+(1.0,+(+(2.0,3.0),4.0))","+(1.0,+(2.0,+(3.0,4.0)))","*(1.0,+(*(2.0,3.0),4.0))","+(+(+(2.0,1.0),3.0),4.0)","+(*(*(2.0,1.0),3.0),4.0)","+(*(/(2.0,1.0),3.0),4.0)","+(+(2.0,+(1.0,3.0)),4.0)","+(*(2.0,*(1.0,3.0)),4.0)","+(/(2.0,/(1.0,3.0)),4.0)","+(+(2.0,1.0),+(3.0,4.0))","+(2.0,+(+(1.0,3.0),4.0))","+(2.0,+(1.0,+(3.0,4.0)))","-(2.0,*(-(1.0,3.0),4.0))","+(+(+(3.0,2.0),1.0),4.0)","+(*(*(3.0,2.0),1.0),4.0)","+(/(*(3.0,2.0),1.0),4.0)","+(+(3.0,+(2.0,1.0)),4.0)","+(*(3.0,*(2.0,1.0)),4.0)","+(*(3.0,/(2.0,1.0)),4.0)","*(+(/(3.0,2.0),1.0),4.0)","+(+(3.0,2.0),+(1.0,4.0))","+(*(3.0,2.0),*(1.0,4.0))","+(3.0,+(+(2.0,1.0),4.0))","+(3.0,+(2.0,+(1.0,4.0)))","+(+(+(2.0,3.0),1.0),4.0)","+(*(*(2.0,3.0),1.0),4.0)","+(/(*(2.0,3.0),1.0),4.0)","+(+(2.0,+(3.0,1.0)),4.0)","+(*(2.0,*(3.0,1.0)),4.0)","+(*(2.0,/(3.0,1.0)),4.0)","+(+(2.0,3.0),+(1.0,4.0))","+(*(2.0,3.0),*(1.0,4.0))","+(2.0,+(+(3.0,1.0),4.0))","+(2.0,*(-(3.0,1.0),4.0))","+(2.0,+(3.0,+(1.0,4.0)))","+(+(+(3.0,1.0),2.0),4.0)","+(*(*(3.0,1.0),2.0),4.0)","+(*(/(3.0,1.0),2.0),4.0)","+(+(3.0,+(1.0,2.0)),4.0)","+(*(3.0,*(1.0,2.0)),4.0)","+(/(3.0,/(1.0,2.0)),4.0)","*(-(3.0,/(1.0,2.0)),4.0)","+(+(3.0,1.0),+(2.0,4.0))","+(-(3.0,1.0),*(2.0,4.0))","+(3.0,+(+(1.0,2.0),4.0))","+(3.0,+(1.0,+(2.0,4.0)))","-(3.0,-(1.0,*(2.0,4.0)))","+(+(+(1.0,3.0),2.0),4.0)","+(*(*(1.0,3.0),2.0),4.0)","+(+(1.0,+(3.0,2.0)),4.0)","+(*(1.0,*(3.0,2.0)),4.0)","*(+(1.0,/(3.0,2.0)),4.0)","+(+(1.0,3.0),+(2.0,4.0))","+(1.0,+(+(3.0,2.0),4.0))","+(1.0,+(3.0,+(2.0,4.0)))","*(1.0,+(*(3.0,2.0),4.0))","+(+(+(4.0,3.0),2.0),1.0)","+(+(4.0,+(3.0,2.0)),1.0)","*(-(*(4.0,3.0),2.0),1.0)","*(+(4.0,*(3.0,2.0)),1.0)","/(-(*(4.0,3.0),2.0),1.0)","/(+(4.0,*(3.0,2.0)),1.0)","+(+(4.0,3.0),+(2.0,1.0))","-(*(4.0,3.0),*(2.0,1.0))","-(*(4.0,3.0),/(2.0,1.0))","+(4.0,+(+(3.0,2.0),1.0))","+(4.0,*(*(3.0,2.0),1.0))","+(4.0,/(*(3.0,2.0),1.0))","+(4.0,+(3.0,+(2.0,1.0)))","+(4.0,*(3.0,*(2.0,1.0)))","+(4.0,*(3.0,/(2.0,1.0)))","*(4.0,+(/(3.0,2.0),1.0))","+(+(+(3.0,4.0),2.0),1.0)","+(+(3.0,+(4.0,2.0)),1.0)","-(+(3.0,*(4.0,2.0)),1.0)","*(-(*(3.0,4.0),2.0),1.0)","/(-(*(3.0,4.0),2.0),1.0)","+(+(3.0,4.0),+(2.0,1.0))","-(*(3.0,4.0),*(2.0,1.0))","-(*(3.0,4.0),/(2.0,1.0))","+(3.0,+(+(4.0,2.0),1.0))","+(3.0,-(*(4.0,2.0),1.0))","+(3.0,+(4.0,+(2.0,1.0)))","+(+(+(3.0,2.0),4.0),1.0)","+(+(3.0,+(2.0,4.0)),1.0)","-(+(3.0,*(2.0,4.0)),1.0)","*(+(*(3.0,2.0),4.0),1.0)","/(+(*(3.0,2.0),4.0),1.0)","+(+(3.0,2.0),+(4.0,1.0))","+(*(3.0,2.0),*(4.0,1.0))","+(*(3.0,2.0),/(4.0,1.0))","+(3.0,+(+(2.0,4.0),1.0))","+(3.0,-(*(2.0,4.0),1.0))","+(3.0,+(2.0,+(4.0,1.0)))","+(+(+(4.0,2.0),3.0),1.0)","+(+(4.0,+(2.0,3.0)),1.0)","-(+(*(4.0,2.0),3.0),1.0)","*(+(4.0,*(2.0,3.0)),1.0)","/(+(4.0,*(2.0,3.0)),1.0)","+(+(4.0,2.0),+(3.0,1.0))","+(*(4.0,2.0),-(3.0,1.0))","+(4.0,+(+(2.0,3.0),1.0))","+(4.0,*(*(2.0,3.0),1.0))","+(4.0,/(*(2.0,3.0),1.0))","+(4.0,+(2.0,+(3.0,1.0)))","+(4.0,*(2.0,*(3.0,1.0)))","+(4.0,*(2.0,/(3.0,1.0)))","+(+(+(2.0,4.0),3.0),1.0)","+(+(2.0,+(4.0,3.0)),1.0)","-(+(*(2.0,4.0),3.0),1.0)","+(+(2.0,4.0),+(3.0,1.0))","+(*(2.0,4.0),-(3.0,1.0))","+(2.0,+(+(4.0,3.0),1.0))","+(2.0,+(4.0,+(3.0,1.0)))","+(2.0,*(4.0,-(3.0,1.0)))","+(+(+(2.0,3.0),4.0),1.0)","+(+(2.0,+(3.0,4.0)),1.0)","*(+(*(2.0,3.0),4.0),1.0)","/(+(*(2.0,3.0),4.0),1.0)","+(+(2.0,3.0),+(4.0,1.0))","+(*(2.0,3.0),*(4.0,1.0))","+(*(2.0,3.0),/(4.0,1.0))","+(2.0,+(+(3.0,4.0),1.0))","+(2.0,+(3.0,+(4.0,1.0)))","+(+(+(4.0,1.0),2.0),3.0)","+(+(4.0,+(1.0,2.0)),3.0)","+(+(4.0,1.0),+(2.0,3.0))","+(*(4.0,1.0),*(2.0,3.0))","+(/(4.0,1.0),*(2.0,3.0))","+(4.0,+(+(1.0,2.0),3.0))","+(4.0,*(*(1.0,2.0),3.0))","+(4.0,+(1.0,+(2.0,3.0)))","+(4.0,*(1.0,*(2.0,3.0)))","+(+(+(1.0,4.0),2.0),3.0)","+(+(1.0,+(4.0,2.0)),3.0)","+(+(1.0,4.0),+(2.0,3.0))","+(*(1.0,4.0),*(2.0,3.0))","+(1.0,+(+(4.0,2.0),3.0))","+(1.0,+(4.0,+(2.0,3.0)))","*(1.0,+(4.0,*(2.0,3.0)))","+(+(+(1.0,2.0),4.0),3.0)","+(+(1.0,+(2.0,4.0)),3.0)","+(+(1.0,2.0),+(4.0,3.0))","+(1.0,+(+(2.0,4.0),3.0))","+(1.0,+(2.0,+(4.0,3.0)))","+(+(+(4.0,2.0),1.0),3.0)","+(-(*(4.0,2.0),1.0),3.0)","+(+(4.0,+(2.0,1.0)),3.0)","+(+(4.0,2.0),+(1.0,3.0))","-(*(4.0,2.0),-(1.0,3.0))","+(4.0,+(+(2.0,1.0),3.0))","+(4.0,*(*(2.0,1.0),3.0))","+(4.0,*(/(2.0,1.0),3.0))","+(4.0,+(2.0,+(1.0,3.0)))","+(4.0,*(2.0,*(1.0,3.0)))","+(4.0,/(2.0,/(1.0,3.0)))","+(+(+(2.0,4.0),1.0),3.0)","+(-(*(2.0,4.0),1.0),3.0)","+(+(2.0,+(4.0,1.0)),3.0)","+(+(2.0,4.0),+(1.0,3.0))","-(*(2.0,4.0),-(1.0,3.0))","+(2.0,+(+(4.0,1.0),3.0))","+(2.0,+(4.0,+(1.0,3.0)))","-(2.0,*(4.0,-(1.0,3.0)))","+(+(+(2.0,1.0),4.0),3.0)","+(+(2.0,+(1.0,4.0)),3.0)","+(+(2.0,1.0),+(4.0,3.0))","+(2.0,+(+(1.0,4.0),3.0))","+(2.0,+(1.0,+(4.0,3.0)))","+(+(+(4.0,1.0),3.0),2.0)","+(+(4.0,+(1.0,3.0)),2.0)","-(*(*(4.0,1.0),3.0),2.0)","-(*(/(4.0,1.0),3.0),2.0)","-(*(4.0,*(1.0,3.0)),2.0)","-(/(4.0,/(1.0,3.0)),2.0)","+(+(4.0,1.0),+(3.0,2.0))","+(*(4.0,1.0),*(3.0,2.0))","+(/(4.0,1.0),*(3.0,2.0))","+(4.0,+(+(1.0,3.0),2.0))","+(4.0,*(*(1.0,3.0),2.0))","+(4.0,+(1.0,+(3.0,2.0)))","+(4.0,*(1.0,*(3.0,2.0)))","*(4.0,+(1.0,/(3.0,2.0)))","+(+(+(1.0,4.0),3.0),2.0)","+(+(1.0,+(4.0,3.0)),2.0)","-(*(*(1.0,4.0),3.0),2.0)","-(*(1.0,*(4.0,3.0)),2.0)","+(+(1.0,4.0),+(3.0,2.0))","+(*(1.0,4.0),*(3.0,2.0))","+(1.0,+(+(4.0,3.0),2.0))","+(1.0,+(4.0,+(3.0,2.0)))","*(1.0,-(*(4.0,3.0),2.0))","*(1.0,+(4.0,*(3.0,2.0)))","+(+(+(1.0,3.0),4.0),2.0)","+(+(1.0,+(3.0,4.0)),2.0)","-(*(*(1.0,3.0),4.0),2.0)","-(*(1.0,*(3.0,4.0)),2.0)","+(+(1.0,3.0),+(4.0,2.0))","+(1.0,+(+(3.0,4.0),2.0))","+(1.0,+(3.0,+(4.0,2.0)))","*(1.0,-(*(3.0,4.0),2.0))","+(+(+(4.0,3.0),1.0),2.0)","+(+(4.0,+(3.0,1.0)),2.0)","+(*(4.0,-(3.0,1.0)),2.0)","-(*(*(4.0,3.0),1.0),2.0)","-(/(*(4.0,3.0),1.0),2.0)","-(*(4.0,*(3.0,1.0)),2.0)","-(*(4.0,/(3.0,1.0)),2.0)","+(+(4.0,3.0),+(1.0,2.0))","-(*(4.0,3.0),*(1.0,2.0))","+(4.0,+(+(3.0,1.0),2.0))","+(4.0,*(*(3.0,1.0),2.0))","+(4.0,*(/(3.0,1.0),2.0))","+(4.0,+(3.0,+(1.0,2.0)))","+(4.0,*(3.0,*(1.0,2.0)))","+(4.0,/(3.0,/(1.0,2.0)))","*(4.0,-(3.0,/(1.0,2.0)))","+(+(+(3.0,4.0),1.0),2.0)","+(+(3.0,+(4.0,1.0)),2.0)","-(*(*(3.0,4.0),1.0),2.0)","-(/(*(3.0,4.0),1.0),2.0)","-(*(3.0,*(4.0,1.0)),2.0)","-(*(3.0,/(4.0,1.0)),2.0)","+(+(3.0,4.0),+(1.0,2.0))","-(*(3.0,4.0),*(1.0,2.0))","+(3.0,+(+(4.0,1.0),2.0))","+(3.0,+(4.0,+(1.0,2.0)))","+(+(+(3.0,1.0),4.0),2.0)","+(*(-(3.0,1.0),4.0),2.0)","+(+(3.0,+(1.0,4.0)),2.0)","-(*(*(3.0,1.0),4.0),2.0)","-(*(/(3.0,1.0),4.0),2.0)","-(*(3.0,*(1.0,4.0)),2.0)","-(/(3.0,/(1.0,4.0)),2.0)","+(+(3.0,1.0),+(4.0,2.0))","+(-(3.0,1.0),*(4.0,2.0))","+(3.0,+(+(1.0,4.0),2.0))","+(3.0,+(1.0,+(4.0,2.0)))","-(3.0,-(1.0,*(4.0,2.0)))"]

検証

検証のため，全ての可能な組み合わせに対して，(制約の弱い方の一般的な)テンパズルの答えを求めてみましょう．
ただし，実際に検証するのは膨大な数になるため，Wikipediaの以下の記述にあるように

一般的なルールとしては、四則演算のみの使用を許可し、数字の並び替えも許可されるが、数字の結合は許可されない。一般的なルールの場合、全715通り中552通りの組み合わせ（並び替えたものを数えると全10000通り中8147通り）で10を作ることができる。

解が存在するパターンが552通りになるかチェックしてみます．

ただし，そのためには，715通りの組み合わせを作り出す関数がいりますね．．．（715という値は，0000〜9999 のうち，並べ替えれば作り出せる４字は同値としてまとめた同値類の数になります．例えば，1234と4321は同値です）．
この手の問題は，重複組み合わせ問題 というのですが， haskell の標準的なライブラリには，どうやらこの重複組み合わせを生成するライブラリが無いようです．（というか，組み合わせもそもそもないけど，組み合わせは簡単にコードがかけます）．
そこで，重複組み合わせを行うコードも書いたのですが，これはこれで解説が長くなりそうなので，この解説は後日別の記事にまとめたいと思います．

comb :: [a] -> Int -> [[a]]
comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) n = let ys = comb xs $ pred n
  in (map (x:) ys) ++ comb xs n

hPro :: [a] -> Int -> [[a]]
hPro xs r = let
  n = pred $ length xs
  m = n + r
  c ys = (\x y-> pred $ x-y) <$> ZipList(ys ++ [succ m]) <*> ZipList(0:ys)
  fromNums ys = concat . getZipList $ (\x y-> replicate y x) <$> ZipList xs <*> c ys
  in map fromNums $ comb [1..m] n

hPro は重複組み合わせを生成する関数です

*Main>  hPro ['a','b','c'] 3
["ccc","bcc","bbc","bbb","acc","abc","abb","aac","aab","aaa"]

これで，テンパズルの解がある条件を全て洗い出すことができます

*Main> length $ filter (/=[]) $ map w10Puzzle $  hPro [0..9] 4
552

よさそうです．
まぁ，分かりきっていますが，以下の確認もしてみましょう．

*Main> let s10 = s10Puzzle [1,2,3,4]
*Main> let w10 = w10Puzzle [1,2,3,4]
*Main> isInfixOf s10 w10
True

まとめ(概要との違いは？というツッコミは無しで．．．)

• カタラン数，いろんなとこにでるから注目していきたい
  • 値を求めるはずだった数式から，組み合わせの生成方法を読み解くことができるので数学凄い
• Haskell だと完結に表現できるから凄い