# Exercise 3.41

Define list transpose as a fold, then as an unfold.

    trans ∷ List (List α) → List (List α)

It would be nice if you told us what the function *does*, Jeremy!

We can specify this function by

    trans Nil = Nil
    trans (Cons xs xss) =
      if nil xs
         then Nil
         else Cons (map head (Cons xs xss))
                (trans (map tail (Cons xs xss)))

However, this version of trans is partial; it’s undefined on lists of
unequal-length lists.  For what we’ll be using it for, it’s critical
that we write the total version.

    trans Nil            = Nil
    trans (Cons Nil xss) = trans xss
    trans xss            = Cons (map head xss') (trans (map tail xss'))
      where xss' = filter (not ∘ nil) xss

This definition is actually a bit subtle.

Let’s try the unfold version first.

(a) Anamorphism

By the universal property of unfoldL, we have

    unfoldL p f g = trans

    iff

    trans xss = if p xss
                  then Nil
                  else Cons (f xss) (trans (g xss))

Since trans xss = Nil iff xss = Nil, we have p = nil.  In the case
xss ≠ Nil, we have

    trans xss = Cons (f xss) (trans (g xss))

But we have a serious problem.  By the definition above,

    trans (Cons Nil Nil) = trans Nil = Nil,

which is not of the form Cons y ys.  So it seems we can’t proceed.

Gibbons really does not provide anywhere near enough information in
this section.  We need a total version of list transpose, but there
does not seem to be a way to define it as an unfold.  (The fold version
seems even more daunting.)