Lists of lists with foldl and replace elements that have occured before?

Given the data types:

type Instructions = [Instruction]
data Piece = Wall | Food Size
data Size = Little | Big
data Instruction = Instruct [(Int, Piece)]
                 | Repeat Int

and a partially compacted maze:

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

you can compact it using recursion. At each recursive step, you need to check if the next [(Int, Piece)] item has already been output (so you can decide if it's a repeat), and to do this, you'll need to keep track of the list of instructions you've output so far. The easiest way to do this, is to make the instructions you've already produced into an argument to your recursive function, so your recursive function will look like this:

compact' :: Instructions -> [[(Int, Piece)]] -> Instructions
compact' done (x:xs) = ...

where the right-hand side of this definition will process the next x :: [(Int, Piece)] using a list of instructions we've already done, namely done :: Instructions.

We'll do this by adding the next instruction to the list already done and recursing:

compact' done (x:xs) = compact' (done ++ [next]) xs

and then, when we run out of input, returning the full list:

compact' done [] = done

The only remaining step is to define next. We can use elemIndex from Data.List to look up the position of x in done, if it's a repeat, like so:

where next = case elemIndex (Instruct x) done of
               Just pos -> Repeat pos

If it isn't found, we just add it as an Instruct instruction:

               Nothing -> Instruct x

To kick things off, we'll write a compact that starts the recursion with an empty done = []:

compact :: [[(Int, Piece)]] -> Instructions
compact input = compact' [] input

which can be written more simply as:

compact = compact' []

Getting the full program to compile requires us to add an appropriate import and some deriving clauses to the data types. (Eq is needed to look the instruction up in the done list.) The full program looks like:

import Data.List

type Instructions = [Instruction]
data Piece = Wall | Food Size deriving (Show, Eq)
data Size = Little | Big deriving (Show, Eq)
data Instruction = Instruct [(Int, Piece)]
                 | Repeat Int
                 deriving (Show, Eq)

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

compact :: [[(Int, Piece)]] -> Instructions
compact = compact' []
  where compact' :: Instructions -> [[(Int, Piece)]] -> Instructions
        compact' done (x:xs) = compact' (done ++ [next]) xs
          where next = case elemIndex (Instruct x) done of
                         Just pos -> Repeat pos
                         Nothing  -> Instruct x
        compact' done [] = done

main = print (compact maze1)

This is not a very efficient implementation, as it runs in quadratic time searching and re-searching the done list for every element added and using done ++ [next] to append an element in linear time. However, you'd have to be writing a pretty enormous pacman game for this bad performance to be a real issue.

An alternative implementation that uses a Map to efficiently look up the positions might look like this. It shows an alternative technique for the recursion where instead of building up a done list and then returning it at the end, we build up a done map but separately return the list, element by element without waiting until the end. The type-level techniques here (e.g., the definition of Compact a parametrized by the type a) are a little more advanced, but you might find the approach interesting. I think most Haskell programmers would consider this a reasonable production-level implementation (though some might use mapAccumL instead of the recursion). Anyway, this is probably how I'd write it in "real code".

import Data.List
import qualified Data.Map as Map

-- A general representation for lists of repeatable objects
type Compact a = [Repeatable a]
data Repeatable a = First a | Repeat Int deriving (Show)

data Piece = Wall | Food Size deriving (Show, Eq, Ord)
data Size = Little | Big deriving (Show, Eq, Ord)

compact :: (Ord a) => [a] -> Compact a
compact = compact' 0 Map.empty
  where compact' :: (Ord a) => Int -> Map.Map a Int -> [a] -> Compact a
        compact' pos done (x:xs) = next : compact' (pos + 1) done' xs
          where (next, done') = case Map.lookup x done of
                  Just pos -> (Repeat pos, done)
                  Nothing  -> (First x, Map.insert x pos done)
        compact' _ _ [] = []

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

main = do
  print (compact maze1)
  print (compact ["it","is","what","it","is"])

The mapAccumL version would look like this:

compact :: (Ord a) => [a] -> Compact a
compact = snd . mapAccumL step (0, Map.empty)
  where step (pos, done) x = ((pos + 1, done'), next)
          where (next, done') = case Map.lookup x done of
                  Just pos -> (Repeat pos, done)
                  Nothing  -> (First x, Map.insert x pos done)

data Whatever = Wall | Empty | Food deriving(Eq, Show)
long = [(1, Wall),(1, Wall),(1, Wall),(1, Empty),(1, Food),(1, Food),(1, Empty),(1, Wall)]

you can do this:

map (\xs@((x,y):_) -> (length xs, y)) $ Data.List.group long

which gives

[(3,Wall),(1,Empty),(2,Food),(1,Empty),(1,Wall)]