## DEV Community

Pete Tsamouris

Posted on • Updated on

# 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
``````

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
``````

Thanks very much for this tutorial! I am trying to learn Unison, so this helps. But the versions with the fold patterns where still above my understanding level. I also don't understand the use of `drop`