Haskell expression for function mutating its surrounding environment?

user_45843 0
Viewed 122

Haskell is a pure functional language, that provides syntax sugar for the equivalent of imperative expressions. For example, this Python code:

def f():
    n = 0
    for i in range(10):
        n += 1
    return n

can be translated line by line into isomorphic Haskell code using monads.

Is the same true of code where a function mutates its surrounding environment? For example:

def f():
    n = 0
    def g():
        nonlocal n
        n += 1
    for i in range(10):
        g()
    return n

Is there a way to translate the above line by line into isomorphic Haskell?

I'm perfectly prepared for the answer to be no, the code needs to be redesigned to do the same thing in a different way. But I figure it's worth asking if there is an isomorphic translation.

functional-programming haskell
2 Answers

You can work with a State to encapsulate changes of State.

In that case your g can thus look like:

import Control.Monad.State.Lazy(State, modify)

g :: State Int ()
g = modify (1+)

then f is also a State that will first set the state to 0 and then run g ten times:

import Control.Monad(replicateM_)
import Control.Monad.State.Lazy(State, get, put)

f :: State Int Int
f = do
    put 0
    replicateM_ 10 g
    get

You can then run f with evalState :: State s a -> s -> a where we provide an initial state and it will return the result of the State s a item, so here the what the get returns:

Prelude Control.Monad.State.Lazy> evalState f 0
10
user_675790

William Van Onsem mentioned the State monad in the comment, which works. You could also refactor this into a tail-recursive function. For example:

module Test (f) where

f :: Int
f = go 0 10 where
  go :: Int -> Int -> Int
  go n 0 = n
  go n i = go (g n) (i-1)
  g n = n+1

This captures the state by making it an argument to the function. It optimizes reasonably well, too. On GHC 8.6.2 with -O3, the relevant part of this compiles to:

.Lc2gN:
        testq %rsi,%rsi
        jne .Lc2gS
        movq %r14,%rbx
        jmp *(%rbp)
.Lc2gS:
        decq %rsi
        incq %r14
        jmp .Lc2gN

You can see that Haskell passes a continuation to which the branch for the terminating case jumps, similar to but not quite the same as how a traditional imperative language pushes a return address onto the stack. Otherwise, this generated code is precisely equivalent to a while or for loop in an imperative language: there’s a test of the termination condition, a body that updates the registers holding the sum and counter, and a jump back to the top of the code block.

This approach works well for many loops in imperative programs, although not all. If the loop has visible side-effects or mutates a large data structure in place, you will need a different solution, such as combining the State monad with IO using StateT.

user_44744190
Related