haskell - 可以在没有显式递归的情况下编写此代码吗？[Project Euler #31 剧透]

Question

这个函数是解决 Project Euler 问题的核心：

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以便 my与您的( )numWays'具有相同的类型。numWays(Num c, Num b, Enum b) => b -> [b] -> c

这里的想法是，我们不是计算一（对于零残差总数）或零（对于非零残差总数）并将它们求和，而是将函数分解为生成残差列表的递归函数，然后（非递归）计算该列表中有多少个零。

这样做的目的是它给我们留下了一个递归函数，我们可以更容易地从中删除递归。