Redundant `let`s in list monadic code

Question

There is a function with bunch of a redundant lets and ←s inside a list monad.

example ∷ (Int, Int, Int, Int, Int)
example = head $ do
  let list1 = [0,1]
  e1 ← list1
  let list2 = φ list1 e1
  e2 ← list2
  let list3 = φ list2 e2
  e3 ← list3
  let list4 = φ list3 e3
  e4 ← list4
  let list5 = φ list4 e4
  e5 ← list5
  return (e1,e2,e3,e4,e5)
    where φ ∷ [Int] → Int → [Int]

So, all list# values are unusable. How can example could be rewritten with >>= or maybe with something else to get (e1,e2,e3,e4,e5) without any lets?

Answer 1

Here's my solution, which uses tuple to keep previous e# with current list together. It doesn't use State or List monad, though you could replace concatMap with =<<, as it's the same thing:

import Control.Arrow
import Data.List

example :: [Int]
example = reverse . fst . head $ lists

φ :: [Int] -> Int -> [Int]
φ = undefined

phi :: ([Int], [Int]) -> [([Int], [Int])]
phi (xs, ys) = map ((:xs) &&& φ ys) ys

list1 = [0, 1]

lists :: [([Int], [Int])]
lists = iterate (concatMap phi) [([], list1)] !! 5

Answer 2

Hm, this could probably be done using foldM or similar, but that would require you to convert to and from lists. My first impulse would be to try to write the top-level of example using Applicative style:

import Control.Applicative

example = head $ (,,,,) <$> m <*> m <*> m <*> m <*> m

But that doesn't work directly here, as you want each m to know the list# of the last action.

One way to realize this without breaking up the above structure would be to have a StateT monad transformer take care of passing around the current list#:

import Control.Monad.State

example = head $ flip evalStateT [0,1] $
          (,,,,) <$> m <*> m <*> m <*> m <*> m

This allows us to write m as a list monad with state:

  where m :: StateT [Int] [] Int
        m = do list <- get
               e <- lift list
               put (phi list e)
               return e

Now admittedly, this is a bit advanced. It might be easier to try to restructure phi or use a foldM type solution.