Stateful version of map (Haskell)

Question

I have just learned about creating higher-order functions and I want to make a map function that is able to change a function that applies to tuples to have that function apply to a list of that type. (Just like the map function.) I am trying to create it in such a way that it has this signature:

statefulMap :: ((a,state) -> (b,state)) -> (([a],state) -> ([b],state))

I want to be able to use this function to create a series of full adders, but how do I create this function in the first place?

What is this function supposed to do? From what I can see it takes a function as an argument and returns another function. I'm having a difficult time understanding how this is like map which has the type (a -> b) -> [a] -> [b]. Note that map takes two parameters. — Code-Apprentice
@Code-Apprentice: no, here the parenthesis are redundant, the two are equal, since the -> operator works right-to-left. — Willem Van Onsem

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2018-01-28T22:24:11

This actually already exists: we can use a state monad and use the monadic version of map: mapM.

For instance we can write a function for a full adder. Here I think with state you mean the carry that the previous full adder has generated.

So we can make a full adder as:

import Control.Monad.State.Lazy

fa :: (Bool, Bool) -> State Bool Bool
fa (a, b) = do
   ci <- get
   let d = a /= b
   put ((ci && d) || (a && b))
   return (ci /= d)

The type means that we make a function that alters state. The first Bool specifies the type of the state itself (here a boolean, the carry that is True or False), the second Bool specifies what we "return" (here a True or False as output for the specific full adder).

Now we can make a stateful map, with mapM:

fullAdders :: [(Bool, Bool)] -> State Bool [Bool]
fullAdders = mapM fa

This thus takes a list of 2-tuples (the inputs for every full adder), and produces a State Bool [Bool], so the state is still a Bool, but the result now is a list of booleans [Bool]: a list that contains the output for every full adder.

We can now call it with fullAdders [(True, True), (True, False), (False, False), (True, True)] but this will not give us a list of booleans, but a State Bool [Bool]. We can the "run" the state monad by specifying the initial state. We can do this by using runState :: State a b -> a -> (a, b), so we can call it with:

runState (fullAdders [(True, True), (True, False), (False, False), (True, True)]) False

this produces:

Prelude Control.Monad.State.Lazy> runState (fullAdders [(True, True), (True, False), (False, False), (True, True)]) False
([False,False,True,False],True)

so a 2-tuple with as first item the result, and as second item the new state (here True, since the carry output of the last full adder will be True).

Stateful version of map (Haskell)

1 Answers