如何在没有手写递归的情况下摆脱Haskell的纯循环? [英] How do I break out of a pure loop in Haskell without hand-written recursion?

问题描述

我想编写一个函数，该函数将遍历列表，更新一个累加器，直到该累加器达到某个条件或到达列表的末尾.例如，产品功能在累加器达到零时立即停止.

I want to write a function that goes through a list updating an accumulator until that accumulator reaches a certain condition or I get to the end of the list. For example, a product function that stops as soon as its accumulator reaches zero.

我知道如何通过手动编写递归来对其进行编码:

I know how to code it by writing the recursion by hand:

{-# 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

但是有没有办法使用折叠和其他高阶函数对此进行编码?

but is there a way to code this using folds and other higher order functions?

想到的一件事就是定义

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

，然后使用foldl'.但是，这并不会很早就解决，因此会浪费一些性能.

and then using foldl'. However, this doesn't break out early so its a bit wasteful of performance.

我们无法使用foldr，因为它以错误的顺序通过列表，并且其及早爆发"的方式是通过查看列表的元素而不是查看累加器(如果累加器的类型与列表元素的类型不同.

We can't use foldr since it goes through the list in the wrong order and its way of "breaking out early" is by looking at the elements of the list instead of looking at the accumulator (this would have mattered if the accumulator had a different type than the list elements).

推荐答案

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

One simple way is to do the computation in a monad that allows to escape early, such as Either or 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，这将立即退出计算.例如，以下立即退出:

At each step of the computation we check if the accumulator is nonzero. And if it's zero, guard invokes mplus, which exits the computation immediately. For example the following exits immediately:

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

这篇关于如何在没有手写递归的情况下摆脱Haskell的纯循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！