17 Apr 2024

Faking a recursive closure in elixir

Recursive closures do not seem to be available in elixir (or erlang). An example discussion is on the elixir forum here. However, I recently had need of such a facility.

Reading Knuth–Morris–Pratt illustrated (Cameron Moy, 2024, Journal of Functional Programming, 34, e3), I thought I would try to port the haskell implementations to elixir.

Here's an example haskell function (based on verticalList from the paper) with a recursive closure:

1: verticalList pattern text = any done (scanl step init text)
2:     where init :: [String]
3:           init = [pattern]
4:           step :: [String] -> Char -> [String]
5:           step [] x = init
6:           step acc@(t:r) x
7:             | check acc x = (tail t):(step r (head t))
8:             | otherwise   = step r x

Ancillary functions done and check are just:

 9: Done ("":_)  = True
10: done _       = False
11: 
12: check (h:_) x = isPrefixOf [x] h
13: check _ _     = False

That step function from lines 4-8 is a recursive closure:

recursive: the function calls itself in lines 7 and 8;
closure: it includes init from the immediate context.

This is not possible in elixir/erlang because the variable name to which the anonymous function is assigned is only defined after the anonymous function body has been parsed. Or something like that. The haskell compiler seems to manage it, …

Anyway, I simulated this recursive closure in elixir by:

extracting the top level step to its own function (lines 12-26 below);
decorating the initial accumulator with the enclosed variable init as a kind of context (line 6);
un-decorating the context from the result (line 7).

 1: def verticalList(pattern, text) do
 2:   init = [pattern]
 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: 
12: def step({init, []}, _x) do
13:   {init, init}
14: end
15: 
16: def step({init, acc = [t | r]}, x) do
17:   case check(acc, x) do
18:     true ->
19:       [ht | tt] = t
20:       {_, acc2} = step({init, r}, ht)
21:       {init, [tt | acc2]}
22: 
23:     false ->
24:       {_, acc2} = step({init, r}, x)
25:       {init, acc2}
26:   end

Elixir doesn't have a built-in equivalent of haskell's scanl so that's added to the ancillary functions:

27: def scanl(_f, acc, []) do
28:   [acc]
29: end
30: 
31: def scanl(f, acc, [x | xt]) do
32:   acc1 = f.(acc, x)
33:   [acc | scanl(f, acc1, xt)]
34: end
35: 
36: def done([~c"" | _]), do: true
37: def done(_), do: false
38: 
39: def check([h | _], x) do
40:   List.starts_with?(h, [x])
41: end
42: 
43: def check(_, _), do: false

In erlang it's a bit less verbose, but otherwise similar:

 1: verticalList(Pattern, Text) ->
 2:     Init = [Pattern],
 3:     Acc = Init,
 4:     Scan = lists:map(fun({_,X}) -> X end,
 5:                      scanl(fun step/2, {Init, Acc}, Text)),
 6:     lists:any(fun done/1, Scan).
 7: 
 8: step({Init, []}, _) ->
 9:     {Init, Init};
10: step({Init, Acc = [T|R]}, X) ->
11:     case check(Acc, X) of
12:         true ->
13:             [HT|TT] = T,
14:             {_, Acc2} = step({Init, R}, HT),
15:             {Init, [TT | Acc2]};
16:         false ->
17:             {_, Acc2} = step({Init, R}, X),
18:             {Init, Acc2}
19:     end.
20: 
21: scanl(_F, Acc, []) ->
22:     [Acc];
23: scanl(F, Acc, [X|Xt]) ->
24:     [Acc | scanl(F, (F(Acc, X)), Xt)].
25: 
26: done([[]|_]) -> true;
27: done(_)      -> false.
28: 
29: check([H|_], X) ->
30:     string:prefix(H, [X]) /= nomatch;
31: check(_, _) ->
32:     false.

Is there a better way to do this?