State Monad style - comp.lang.haskell

Message from discussion State Monad style

daucl...@gmail.com

View profile

More options Nov 14 2007, 12:30 pm

Newsgroups: comp.lang.haskell

From: daucl...@gmail.com

Date: Wed, 14 Nov 2007 17:30:13 -0000

Local: Wed, Nov 14 2007 12:30 pm

Subject: State Monad style

  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

Hello, all,

Working at state monad again. Wikipedia (http://en.wikipedia.org/wiki/
Ackermann_function) gives the standard definition of the Ackermann
function:

> a :: Integer -> Integer -> Integer
> a m n | m == 0 = n + 1
> | m > 0 && n == 0 = a (m - 1) 1
> | m > 0 && n > 0 = a (m - 1) (a m (n - 1))

After running it, I immediately thought of using the State monad to
memo intermediate results (sort of a top-down dynamic programming
approach):

> type AckMap = Map (Integer, Integer) Integer
> type AckMapS = State AckMap Integer
> ackify :: Integer -> Integer -> AckMapS
> ackify m n = do mappo <- get
> case Map.lookup (m, n) mappo of
> Just num -> return num
> Nothing -> ackify' m n

now we need to recursively update the map

> ackify' :: Integer -> Integer -> AckMapS
> ackify' m n | m == 0 = return (n + 1) >>= ackify'' m n
> | m > 0 && n == 0 = ackify (m - 1) 1 >>= ackify'' m n
> | m > 0 && n > 0 =
> ackify m (n - 1) >>= ackify (m - 1) arg >>= ackify'' m n
> ackify'' :: Integer -> Integer -> Integer -> AckMapS
> ackify'' m n ans = do mappo <- get
> put (Map.insert (m, n) ans mappo)
> return ans

... and that works fine (ackify' is my monadic version of my Ackermann
function 'a'), speeding up the computation exponentially, it seems to
me.

My question is, am I violating any principles of monadic style or
brevity? If so, where are the guides for me to correct my style? Put
another way: what are better ways to use Haskell programming
techniques (monads or otherwise) here to increase function 'a's
efficiency while keeping its declarative nature intact?

Sincerely,
Doug Auclair

BTW, wikipedia has a HO functional definition that transliterates to
Haskell very nicely:

> ack :: Integer -> Integer -> Integer
> ack 0 = succ
> ack m = iter $ ack (m - 1)
> iter :: (Integer -> Integer) -> Integer -> Integer
> iter f 0 = f 1
> iter f n = f $ iter f (n - 1)

(perhaps the wikipedia def has an error, but that's not a propos to
this discussion)

Forward