Find the last element of a list

Disclaimer

I decided to join the community of people currently helping alphatest the Unison programming language. At this point in time, the standard library is actively being worked on. I will embark on solving the 99 Haskell problems in unison, and try and make implementation notes, tailored for a beginner friendly audience. There is little expectation on my part that I will actually make it all the way to 99.

Some familiarity with concepts like recursion, tail recursion, pattern matching and functional programming might be necessary to follow the code. I have made the effort on my part to embed relevant links, as the post progresses, while at the same time removing abilities from the type signatures. One of the points of the 99 exercises is to try as many alternative implementations: I will attempt to go out of my way and explore alternatives, even if a faster, more obvious, or easier approach is readily available.

Exercise 1: Find the last element of a list

So what can I work with?

unison has a unique approach to type declarations: types are identified by their hash, and not their name. As per the snippet here, I am using Maybe/Just/Nothing for the Option a type.

As of ucm release 1g a quick find on base.List reveals the following:

.> find base.List
base.List.++        base.List.drop      base.List.insert    base.List.slice     base.List.unsnoc
base.List.+:        base.List.empty     base.List.join      base.List.snoc      base.List.zip
base.List.:+        base.List.flatMap   base.List.map       base.List.sortBy    base.List
base.List.at        base.List.foldb     base.List.range     base.List.take
base.List.cons      base.List.foldl     base.List.replace   base.List.uncons
base.List.diagonal  base.List.halve     base.List.reverse   base.List.unfold
base.List.distinct  base.List.indexed   base.List.size      base.List.unsafeAt

Coming from other programming languages that implement cons lists, my expectation was that the code would be more or less implemented as a pattern match, involving use of the cons constructor (::). However, at the time of writing, the language reference around pattern matching on lists was not available.

Simple recursion using uncons

Let's briefly see what uncons does:

.> find base.List.uncons
  1. base.List.uncons : [a] -> Maybe (a, [a])

Given a list of as, uncons returns a Maybe (a, [a]) tuple of the head and tail of the list (the tail itself being a list). Using uncons, the first recursion clause will be Nothing for an empty list. There is no last element in this case, so the function returns Nothing. In the case of a head element followed by a tail, the recursion ends when, peeking into the tail, it is found empty, the head thus being the last element of the list. If the tail does contain more elements, the function recurses into the tail, till a result is found.

last: [a] -> Maybe a
last xs = case uncons xs of
  Nothing -> Nothing
  Just (a, []) -> Just a
  Just (a, as) -> last as

But does my function work? (aka unit and property tests)

Using the (very straightforward turns out) testing framework of unison, some quick tests prove that the function works as anticipated:

test> last.empty = run( expect( last [] == None))
test> last.nonEmpty = run( expect( last [1] == Just 1))
test> last.prop.last =
  go _ = a = !(list nat)
         b = !nat
         expect( (last (a ++ [b])) == Just b)
  runs 100 go
test> last.empty = run( expect( last [] == None))
✅ Passed : Passed 1 tests. (cached)
test> last.nonEmpty = run( expect( last [1] == Just 1))
✅ Passed : Passed 1 tests. (cached)
go _ = a = !(list nat)
✅ Passed : Passed 100 tests. (cached)

I think there's more in base.List

Turns out there's another interesting function in base.List, unsnoc, which I actually at first glance overlooked:

.> find base.List.unsnoc

  1. base.List.unsnoc : [a] -> Maybe ([a], a)

Given a list of as, unsnoc (maybe) breaks the list into: a list containing all but the last element, and the last element. At which point the last element, needs to just be extracted from the tuple:

last: [a] -> Maybe a
last xs = map at2 (unsnoc xs)

How about a more 'formal' or 'generic' way of doing any of this?

The fold pattern is used to generalize over recursion (and tail recursion, more on these to follow).

Let's briefly see what foldb does:

.> find base.List.foldb
  1. base.List.foldb : (a -> b) -> (b -> b -> b) -> b -> [a] -> b
.> view base.List.foldb
  base.List.foldb : (a -> b) -> (b -> b -> b) -> b -> [a] -> b
  base.List.foldb f op z as

In a (very) generic way, given a function f to apply, and an operator op, foldb will convert a list of a to a list of b, using a default term z as the beginning (and end, if the list is empty).

Caring only to get the last element of a list, the default z is Nothing, the f provides a way to box elements in a Just and the op only cares to keep track of the last element seen:

(a -> Maybe a) ->                  Just 
(Maybe a -> Maybe a -> Maybe a) -> (x -> y -> y) 
Maybe a ->                         Nothing 
[a] ->                             xs
b  

last: [a] -> Maybe a
last xs = foldb Just (x -> y -> y) Nothing xs

How about 'tail recursion'?

Quick mention: If a function can be written in terms of recursion, in certain programming languages, the compiler can optimise the calls to an iteration, if the function is rewritten in a tail recursive manner.

The intention at this point is not to assess whether the compiler indeed optimises tail recursive calls, but to reimplement the definition of last.

Let's briefly see what foldl does:

.> find base.List.foldl
  1. base.List.foldl : (b -> a -> b) -> b -> [a] -> b
.> view base.List.foldl
  base.List.foldl : (b -> a -> b) -> b -> [a] -> b
  base.List.foldl f z as

In an analogous to foldb manner, foldl will require a z term, as well as an f, which in this case keeps track of the last element. Notice that boxing in a Just, happens as the elements are iterated over.

(b -> a -> b) ->                  (x -> y -> Just y)
b ->                              Nothing
[a] ->                            xs
b

last: [a] -> Maybe a
last xs = foldl (x -> y -> Just y) Nothing xs

The unison way!

I reached out to the alphatesting slack channel for unison, and Paul Chiusano pointed out that the base.List data structure in unison is implemented in terms of a finger tree. There is no need to go over the entire list, since the finger tree provides constant amortized time access to the (first and) last element.

.> find base.List.size
  1. base.List.size : [a] -> Nat
.> find base.List.at
  1. base.List.at : Nat -> [a] -> Maybe a

List.size returns a Nat of the size of the list, which then needs to be dropped by one, since the list is indexed from 0 to (size - 1).

last: [a] -> Maybe a
last xs = List.at (List.size xs `drop` 1) xs

So what would be the "suggested approach"?

unsnoc, mentioned above, is probably the best balance between a convenient return signature, O(1) access to either end of the underlying finger tree, simple and straightforward use at the callsite. And for the curious ones, here's a quick peak into what it actually does:

.> view base.List.unsnoc
  base.List.unsnoc : [a] -> Maybe ([a], a)
  base.List.unsnoc as =
    i = List.size (List.drop 1 as)
    case List.at i as of
      None -> None
      Just a -> Just (List.take i as, a)

Final note:

I have avoided a more advanced coding style on purpose. For reference, lambdas parameters to be ignored can be substituded by _, and function arguments (like xs) can be dropped on both the left and right hand side of the definition.

last = foldb Just (_ -> y -> y) Nothing
last' = foldl (_ -> y -> Just y) Nothing