Is there no O(1) head function?

[turion]

After reading the original article by Ross & Paterson, I came across the part where they talk about how the performance differs slightly for strict languages as compared to lazy languages. One situation is the head function. In a lazy language, one simply defines head in terms of view_l. But this only has O(1) complexity because the computation of the tail is lazy. In a strict language such as elixir, view_l (

hallux/lib/hallux/internal/finger_tree.ex

Line 215 in 1b154f7

def view_l(%Empty{}), do: nil

) builds up the tail completely, taking O(n), and then in the case of head drops it again.

There are two ways out of this:

1. Manual laziness annotations using closures for the :m field in the %Deep{} struct
2. An extra head function that doesn't compute the tail

Option 2. adds some duplicated code and only patches this particular function, but option 1. requires changes in the whole Fingertree module.

[thalesmg]

Very good point! If one is to implement head here (and tail as well), they would suffer from that.

1. Manual laziness annotations using closures for the :m field in the %Deep{} struct
2. An extra head function that doesn't compute the tail

Option (2) is very pragmatic for Elixir (and is even a suggestion from the original paper).

Regarding option (1), if I understood the suggestion correctly, view_{l,r} would return, when non-empty, the head/tail plus a closure that will produce the remaining tree, right?

Option (1) seem quite attractive and elegant. It'll just make the API a bit clunkier to use, since the user will have to manually force the returned "thunk" when using view_{l,r} directly if they are interested in it. Which would make it a breaking change as well. Not that it is much of a problem: that only requires a major version bump when releasing.

I'd view option (2) as a quicker and good enough solution for now, if one needs to implement that function. After that, (1) would be a possible further improvement on that.

[turion]

Regarding option (1), if I understood the suggestion correctly, view_{l,r} would return, when non-empty, the head/tail plus a closure that will produce the remaining tree, right?

No, it's simpler than that. The laziness resides in the %Deep{} struct completely. Evaluating the thunk is always done internally, whenever a function needs to inspect the recursive :m field. view_{l,r} still returns a normal finger tree, there should be no change in the API. (I haven't tried yet though whether everything works out.)