Does this `List.unzip` implementation have anything to do with the fixed-point combinator?

Help
#1

I’m working my way through Functional Programming Made Easier’s exercises of re-implementing some of the functions in Data.List. Had quite the hard time understanding takeEnd and dropEnd, but unzips implementation in the book baffled me completely,

unzip :: ∀ a b. List (Tuple a b) -> Tuple (List a) (List b)
unzip Nil = Tuple Nil Nil
unzip (Tuple x y : ts) =
  unzip ts # \(Tuple xs ys) -> Tuple (x : xs) (y : ys)

until I rewrote it slightly:

unzipMine :: forall a b. List (Tuple a b) -> Tuple (List a) (List b)
unzipMine Nil = Tuple Nil Nil
unzipMine (Tuple x y : ts) = t (unzipMine ts)
  where
    t (Tuple xs ys) = Tuple (x : xs) (y : ys)

Is my intuition correct that this is an application of the fixed-point combinator?

At least, expanding the call

uz = unzipMine
uz (Tuple "a" 1 : Tuple "b" 2 : Nil)
( \(Tuple xs ys) -> Tuple ("a" : xs) (1 : ys) ) (uz (Tuple "b" 2 : Nil)
--------------t1-------------------------------
t1 (( \(Tuple xs ys) -> Tuple ("b" : xs) (2: ys) ) (uz Nil))
    ----------t2----------------------------------
t1 ( t2 (uz Nil))

resembles

fix f = f (fix f)

(This also reminded me a lot of when I read about how overriding packages in Nix works, but then Nix is a lazy language.)

TL;DR

My first foray into FP was through Erlang and writing tail-recursive functions was always easier. I mostly avoided other kinds, but I’m starting to grasp how powerful the above approach is - even though I’m still struggling to wrap my head around it. My implementation of unzip was

unzipMine' :: forall a b. List (Tuple a b) -> Tuple (List a) (List b)
unzipMine' ts = Tuple (go fst ts) (go snd ts)
  where
    go _ Nil = Nil
    go f (t : ts') = f t : go f ts'

which looks way more “Erlang-y” and not sure how it compares to the above in efficiency.

1 Like
#2

Hi,

not sure if I get the question correctly but yes when you’ve got a recursive definition you can write a version of it using fix (which in some sense does the recursion for you and so it’s usually not that interesting unless you need a version where - for example - you want some help in correctly weaving effects in).

Also your last version is not tail-recursive (go is not - the result is used in f t : _) if you want a tail-recursive version you can push this on the heap by using - for example - an additional accumulator parameter:

unzipMine' :: forall a b. List (Tuple a b) -> Tuple (List a) (List b)
unzipMine' ts = Tuple (go [] fst ts) (go [] snd ts)
  where
    go acc _ Nil = reverse acc
    go acc f (t : ts') =  go (f t : acc) f ts'
1 Like
#3

Thank you for trying to make sense of my ramblings!

Well, I got over-excited last night and (after looking deeper into Nixpkgs’ lib.fix again) I’m pretty sure I’ve been conflating ideas. The implementation of unzipMine was using a technique I haven’t seen before, so I think that I was trying to classify the types of recursive function (e.g., something like this) without realizing. Even after years using recursion, it still feels like black magic.

Thanks for the clarification! Didn’t mean to imply that unzipMine' is tail-recursive, but after reading my post again, I realized that I inadvertently did…

#4

Don’t worry I was wondering if you assumed tail-recursion on your last one (turns out I did not get it right).

I can see how the “type of recursion” (linear, etc.) might be helpful if you do an analysis on the algorithm used but when it comes to things like fix the most important thing is that the function wants to call itself (at least that’s the way I approach problems: If I can break a problem down into a smaller/similar version I am drawn to recursion. If the data-structure I’m working with is recursive I’m drawn into recursion, …).

Let me/us know if we can help out with anything more or if you want to discuss things further.

1 Like
#5

To write it in terms of a fixed-point you need to factor out the recursion. A fixed-point combinator gives control to some higher-order function in such a way that it progresses recursively. Your function is still just standard recursion. If you substitute your function t, you get the exact thing as the original. If you have a recursive function already, you can mechanically transform it by replacing all recursive calls to that of some higher-order function parameter. For example:

unzip = case _ of
  Nil ->
    Tuple Nil Nil
  Tuple x y : zs -> do
    let Tuple xs ys = unzip zs -- recursive call
    Tuple (x : xs) (y : ys)

Replacing the recursive call to unzip with a new parameter f yields:

unzipF f = case _ of
  Nil ->
    Tuple Nil Nil
  Tuple x y : zs -> do
    let Tuple xs ys = f zs -- non-recursive call
    Tuple (x : xs) (y : ys)

One can then define some fixed-point function such as:

-- eta-expansion of argument `a` is necessary due to strictness.
fix f a = f (fix f) a

Then you can derive your recursive function:

unzip = fix unzipF

You can step through that substitution:

fix unzipF
\a -> unzipF (fix unzipF) a
\a -> unzipF (\a2 -> unzipF (fix unzipF) a2) a
\a -> unzipF (\a2 -> unzipF (\a3 -> unzipF (...) a3) a2) a

You can see why the eta-expansion of the argument a is necessary due to strictness. That way, it only unrolls to the next step when you apply the argument. If we didn’t eta-expand it, it would immediately unroll forever, diverging while trying to construct the fixed-point.

fix f = f (fix f)
unzip = fix unzipF

fix unzipF
unzipF (fix unzipF)
unzipF (unzipF (fix unzipF))
unzipF (unzipF (unzipF (...)) -- immediately diverges due to strictness.
1 Like
#6

Thank you both for the answers and for the support! I’ve been obsessed with trying to understand overrides in Nixpkgs where the underlying mechanism is using fixed points, so thanks again for providing more pieces of the puzzle.

This (plus the code demonstration below) were super helpful (although still haven’t gotten to do yet), and I’m surprised that I have never seen this stated so succinctly and clearly. (Perhaps I wasn’t able to figure out from the context at the time.)

I think this is just a “coping mechanism” of trying to make sense of the disconnect why some (relatively simple) recursive problems make me struggle hard while I can come up with multiple solutions to others that look more complex. I also tend to over-think stuff, so probably the best is to just keep at it and ask questions when stuck.

Will have to ingest all this in multiple runs, and will probably necrobump this thread with questions once I have progressed more with PureScript, so apologies in advance…:slight_smile: Thanks again!