4

m整数を取り、その行までのパスカルの三角形の行を返す関数を作成しようとしていますm。

choose2 つの整数 n と k を取り、値 n choose k を返す関数を既に作成しました。たとえば、choose 3 23 を返します。

これまでのところ、私は

pascal 0 = [1]
pascal m = [x | x <- pascal (m-1)] ++ [choose m k | k <- [0,1..m]

これは 1 つの大きなリストを返していますが、実際には、各リストがパスカルの三角形の行に対応するリストのリストが必要です。たとえば、pascal 3を返す必要があり[[1],[1,1],[1,2,1],[1,3,3,1]]ます。現在返品中[1,1,1,1,2,1,1,3,3,1]です。

4

1 に答える 1

12

解決策があり、解決策があります。最初に解決策から始めて、解決策に向かって進みましょう。

最初に観察することは、あなたが主張した結果が必要な場合は、型を変更し、もう少しラッピングを行う必要があるということです:

-- was pascal :: Integer -> [Integer]
pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal m = [x | x <- pascal (m-1)] ++ [[choose m k | k <- [0,1..m]]]

さて、いくつかの[x | x <- foo]構文ポインタ:foo[0,1..m][0..m]

pascal m = pascal (m-1) ++ [[choose m k | k <- [0..m]]]

これにより、再帰呼び出しごとに別のリストの末尾にシングルトン リストが追加されていることがわかります。これは非効率的です。前からリストを作成する方がよいでしょう。したがって、一般的なリファクタリングを使用します。アキュムレータを使用してヘルパーを作成します。

pascal = go [] where
    go 0 acc = [1] : acc
    go m acc = go (m-1) ([choose m k | k <- [0..m]] : acc)

次の観察は、毎回再計算するよりも少し効率的に物事を行うことができるということですchoose m k: 前の行といくつかの加算のみを使用して、パスカルの三角形の次の行を計算できます。これは、パスカルの三角形のすべての行の遅延 (無限) リストを作成できることを意味します。

nextRow vs = [1] ++ zipWith (+) vs (tail vs) ++ [1]
allPascals = iterate nextRow [1]

最後に、パスカルの三角形のすべての行はその中点に対して対称であるため、各行の前半だけの無限リストを作成しようとする場合があります。これには、残りの「リストの最後に追加」操作を排除するという利点があります。これは演習として残します。行は偶数の要素と奇数の要素の間で交互に配置されることに注意してください。これにより、この部分が少しトリッキー (かつ醜い) になります。

于 2012-09-13T23:41:35.750 に答える