Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?


One thing that comes to mind is defining

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

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

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).

like image 422
hugomg Avatar asked Jan 20 '14 15:01

hugomg


People also ask

Does Haskell have loops?

Loops in Haskell are implemented using recursion. Since Haskell doesn't have a built-in function of loops like other languages, we'll implement a substitute using recursion.

What is recursion in Haskell?

Recursive functions play a central role in Haskell, and are used throughout computer science and mathematics generally. Recursion is basically a form of repetition, and we can understand it by making distinct what it means for a function to be recursive, as compared to how it behaves.

Does Haskell have stack?

Stack is a tool to build Haskell projects and manage their dependencies. It uses the Cabal library but with a curated version of the Hackage repository called Stackage. Stack competes against Cabal's binary cabal-install and has been created as a result of the overall criticism about dependency problems.


1 Answers

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

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
like image 71
Petr Avatar answered Sep 29 '22 17:09

Petr