haskell - このコードは明示的な再帰なしで記述できますか？[プロジェクトオイラー＃31スポイラー]

Question

この関数は、プロジェクトオイラー問題の解決策の中心です。

numWays tot (d:ds) = sum $ map (flip numWays ds . (tot -)) [0, d .. tot]
numWays tot []
    | tot == 0     = 1
    | otherwise    = 0

明示的な再帰なしで書き直すことができると信じたいのですが、再帰がマップの下にあるという事実は、それを見つけるための私の努力を妨げています。

Answer 1

import Data.List (genericLength)

numWays' tot = genericLength . filter (== 0) . foldl snoc [tot] where
        snoc tots d = concatMap f tots where
                f tot = map (tot -) [0, d .. tot]

genericLength代わりに、あなたの（ ）と同じタイプにlengthなるように使用します。numWays'numWays(Num c, Num b, Enum b) => b -> [b] -> c

ここでの考え方は、1（残差合計がゼロの場合）または0（残差合計がゼロ以外の場合）をカウントして合計する代わりに、関数を再帰関数に分解して残差のリストを生成し、次に（非再帰的に）そのリストにあるゼロの数を数えます。

これを行うことのポイントは、再帰をより簡単に削除できる再帰関数が残ることです。