In functional programming, we use a lot recursion to iterate on datastructure. There is many kind of recursion, some of them can trigger a stack overflow.

I read in the internet that a good use of zipper approach can help in avoiding to use non tail recursion for some use cases, like when implementing a tree.

Honestly a well balanced tree doesn't use a lot the stack. Useful or not, knowing zipper approach can help in doing tail recursion in some tricky use cases, raised my curiosity.

Let's play with a zipper of a list to start

Globally when you are iterating in a recursive datastructure, you can forget easily old visited values, the idea is to integrate a stack for recording parents records.

Here a small code I wrote to play with it :

type 'a t = 'a list * 'a list

let empty = ([], [])

let append x (la,lb) = ([],x :: la @ lb)

let next (la,lb) = 
  let value = List.hd lb in
  (
    value,
    (value::la,List.tl lb)
  )

let previous (la,lb) =
  let value = List.hd la in
  (
    value,
    (List.tl la, value :: lb)
  )

What is intersting is that I can go forward or backward on the list. And this without a double link which imply a mutability.

Here a session in an OCaml interpreter

# let data = empty |> append 1 |> append 2 |> append 3 |> append 4 |> append 5;;
val data : 'a list * int list = ([], [5; 4; 3; 2; 1])

# data |> next;;
- : int * (int list * int list) = (5, ([5], [4; 3; 2; 1]))

# data |> next |> snd |>next;;
- : int * (int list * int list) = (4, ([4; 5], [3; 2; 1]))

# data |> next |> snd |> next |> snd |> next;;
- : int * (int list * int list) = (3, ([3; 4; 5], [2; 1]))

# data |> next |> snd |> next |> snd |> next |> snd |> previous ;;
- : int * (int list * int list) = (3, ([4; 5], [3; 2; 1]))

# data |> next |> snd |> next |> snd |> next |> snd |> previous |> snd |> previous;;
- : int * (int list * int list) = (4, ([5], [4; 3; 2; 1]))

# data |> next |> snd |> next |> snd |> next;;
- : int * (int list * int list) = (3, ([3; 4; 5], [2; 1]))

# data |> next |> snd |> next |> snd |> previous;;
- : int * (int list * int list) = (4, ([5], [4; 3; 2; 1]))

I don't undestand all what is implied. What I see is that combining very simple data structures enable very powerful features, this is a goog example of the Keep It Simple and Stupid principle benefit.