如何在没有手写递归的情况下打破Haskell中的纯循环？

Question

我想写一个函数,通过一个列表更新累加器,直到累加器达到某个条件或我到达列表的末尾.例如,产品功能在其累加器达到零时立即停止.

我知道如何通过手工编写递归来编写代码:

{-# LANGUAGE BangPatterns #-}

prod :: [Integer] -> Integer
prod xs =
    go 1 xs
  where
    go 0   _       = 0
    go !acc []     = acc
    go !acc (x:xs) = go (acc * x) xs

但有没有办法使用折叠和其他更高阶函数来编码？

---

想到的一件事是定义

mult 0 _ = 0
mult x y = x * y

然后使用foldl'.然而,这并没有提前爆发,因此它有点浪费性能.

我们不能使用foldr,因为它以错误的顺序通过列表,它的"早期爆发"的方式是通过查看列表的元素而不是查看累加器(如果累加器有一个,这将是重要的不同于列表元素的类型).

Answer 1

一种简单的方法是在monad中进行计算,允许提前转义,例如:Either或Maybe:

{-# LANGUAGE BangPatterns #-}
import Data.Functor ((<$))
import Data.Maybe (fromMaybe)
import Control.Monad

prod :: [Integer] -> Integer
prod = fromMaybe 0 . prodM

-- The type could be generalized to any MonadPlus Integer
prodM :: [Integer] -> Maybe Integer
prodM = foldM (\ !acc x -> (acc * x) <$ guard (acc /= 0)) 1

在计算的每一步,我们检查累加器是否非零.如果它为零,则guard调用mplus,立即退出计算.例如,以下退出:

> prod ([1..5] ++ [0..])
0

Answer 2

它似乎scanl是最简单的列表组合器,可以为您提供所需的内容.例如,这不会评估第二个列表的1to 10.

Prelude> let takeUntil _ [] = []; takeUntil p (x:xs) = if p x then [x] else (x: takeUntil p xs)
Prelude> (last . takeUntil (==0) . scanl (*) 1) ([1..10] ++ [0..10])
0

takeUntil似乎不存在于标准库中.它就像是,takeWhile但也给你第一个失败的元素.

如果你想要做到这一点,你应该注意那部分last.如果你想要一个强大的通用解决方案,我想mapAccumL是可行的方法.