19 Apr 2024

Elixir: resolve circularity with laziness!

Following on from my recent post on Knuth–Morris–Pratt illustrated, here is another perfectly acceptable haskell function (copied verbatim from the paper):

 1: mp pattern text = any done (scanl step init text)
 2:     where make :: String -> Tree String -> Tree String
 3:           make "" r = Node "" Nil r
 4:           make t r = Node t n r
 5:              where n = make (tail t) (step r (head t))
 6:           init :: Tree String
 7:           init = make pattern Nil
 8:           step :: Tree String -> Char -> Tree String
 9:           step Nil x = init
10:           step acc@(Node t n r) x
11:             | check acc x = n
12:             | otherwise   = step r x
13:

With the Tree type, and done & check as:

14: data Tree a = Nil | Node { top :: a, next :: Tree a, rest :: Tree a }
15: 
16: done Nil = False
17: done acc = (top acc) == ""
18: 
19: check Nil x = False
20: check acc x = isPrefixOf [x] (top acc)

As well as the recursive closure step, mentioned last time, in mp we have circularity. As the paper puts it, "init is defined in terms of make (line 7), which calls step (line 5), which returns init in the base case (line 9)". This is a challenge for an eager language like elixir.

My solution was to enforce laziness to break the circularity. As the paper puts it again (as well as the haskell implementation, Moy offers an implementation in Racket), "only next needs to be lazy."

One (the?) way to implement laziness in elixir is to use funs: instead of a function eagerly returning the expected value, it returns a fun which will return the value when called. This fun can break circularity by taking the problematic variable as an argument.

Porting mp above to elixir, the main mp/2 is similar to last time's verticalList/2:

 1: def mp(pattern, text) do
 2:   init = make(pattern, nil)
 3:   acc = init
 4: 
 5:   scan =
 6:     scanl(&step/2, {init, acc}, text)
 7:     |> Enum.map(fn {_, x} -> x end)
 8: 
 9:   Enum.any?(scan, &done/1)
10: end
11:

make/2 breaks circularity by lazily returning a fun for next, which step/2 then calls, with init:

12: def make(t, r) do
13:   nf = fn init ->                      # next fun created here, ...
14:     [ht | tt] = t
15:     {_, s} = step({init, r}, ht)
16:     make(tt, s)
17:   end
18: 
19:   %KNode{top: t, next: nf, rest: r}    # ... returned here, ...
20: end
21: 
22: def step({init, nil}, _x) do
23:   {init, init}
24: end
25: 
26: def step({init, acc = %KNode{top: _t, next: nf, rest: r}}, x) do
27:   case check(acc, x) do
28:     true ->
29:       n = nf.(init)                    # ... and called here.
30:       {init, n}
31: 
32:     false ->
33:       {_, acc2} = step({init, r}, x)
34:       {init, acc2}
35:   end
36: end

done/1 and check/2:

37: def done(nil), do: false
38: def done(node), do: node.top == ~c""
39: 
40: def check(nil, _x), do: false
41: def check(node, x), do: List.starts_with?(node.top, [x])

With the struct KNode (spelt to avoid warnings) in its own module:

defmodule KNode do
  defstruct top: nil, next: nil, rest: nil
end