Find the last element of a list
Tags: unison, recursion, list, alphatesting
Published: 2019-12-18 17:37:23

#### Disclaimer

I decided to join the community of people currently helping `alphatest` the [`Unison`](https://www.unisonweb.org/) programming language. At this point in time, the standard library is actively being worked on. I will embark on solving the [`99 Haskell problems`](https://wiki.haskell.org/H-99:_Ninety-Nine_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`](https://www.unisonweb.org/docs/language-reference#abilities-and-ability-handlers) 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] (https://www.unisonweb.org/docs/language-reference/#unique-types), 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:
```haskell
.> 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](https://en.wikipedia.org/wiki/Cons), 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](https://www.unisonweb.org/docs/language-reference/pattern-matching).


##### Simple recursion using `uncons`

Let's briefly see what `uncons` does:
```haskell
.> 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.

```haskell
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](https://www.unisonweb.org/docs/tour#testing-your-code) of `unison`, some quick tests prove that the function works as anticipated:
```haskell
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:
```haskell
.> 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:
```haskell
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`](https://en.wikipedia.org/wiki/Fold_(higher-order_function)) is used to generalize over recursion (and tail recursion, more on these to follow).

Let's briefly see what `foldb` does:
```haskell
.> 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:
```haskell
(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`](https://wiki.haskell.org/Tail_recursion) 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:
```haskell
.> 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.
```haskell
(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](https://github.com/pchiusano) pointed out that the `base.List` data structure in `unison` is implemented in terms of a [`finger tree`](https://en.wikipedia.org/wiki/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. 

```haskell
.> 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)`.

```haskell
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:
```haskell
.> 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.

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