Palindromes
Tags: unison, list, tdd, alphatesting
Published: 2019-12-28 13:42:45

#### Disclaimer
As per the [previous post](https://dev.to/petets/an-adventure-in-alpha-testing-3kfn) in this series, in the process of helping out the community of people `alphatesting` the [`Unison`](https://www.unisonweb.org/) programming language, I am solving the [`99 Haskell problems`](https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems) in `unison`, and making notes, tailored for a beginner-friendly audience.

One of the points of the `99 exercises` is to try alternative implementations: I will go out of my way (within reason) and explore such alternatives, even if a faster, more obvious, or easier approach is readily available. Jumping ahead from exercise 1 straight to exercise 6.

#### Exercise 6: Find out whether a list is a palindrome

A definition of a [`palindrome`](https://en.wikipedia.org/wiki/Palindrome) can be found on Wikipedia.

##### Could you follow a "unison workflow" this time?

I previously touched on two `ucm` commands: `find` and `view`, which allow finding functions in the current codebase, and seeing their implementation as stored by the codebase manager.

In this post I will do showcase the Unison workflow (or my understanding/interpretation of it), by means of the `add`, `update`, `test` and potentially other `ucm` commands.

To follow along you will need:
* the Unison codebase manager [`ucm`](https://github.com/unisonweb/unison/releases). Optionally in the `$PATH`.
* A new project created with `ucm -codebase path init`.
* `ucm` running on your target `codebase`: `ucm -codebase path`.
* The `standard library` (called `base`), cloned (from inside `ucm`): `pull https://github.com/unisonweb/base .base`.
* An editor of your choice to open `scratch.u`, under the `codebase` location: `ucm` will pick up any changes to the [`scratch file`](https://www.unisonweb.org/docs/tour#unisons-interactive-scratch-files), and provide output as necessary.

##### Why Unison?

One of the selling points of `Unison` is that `code is content-addressed and immutable`. I would advise taking a close look into [the guide](https://www.unisonweb.org/docs/tour#%F0%9F%A7%A0-the-big-technical-idea) for a more in-depth explanation.

In practice and in short: `names` do not matter. The compiler keeps track of the `abstract syntax tree` representation of the code only, addressing the `hashes` and not the `names` of other functions and values.

No more code formatting or renaming vals and functions. To begin.

##### Can you write tests beforehand?

Fan of [`TDD`](https://en.wikipedia.org/wiki/Test-driven_development)? Let's begin by adding a number of lists some being and some not being palindromes. 

```haskell
passing: [[Nat]]
passing =
  [
    [],
    [1],
    [1, 1],
    [1, 1, 1],
    ...
    [1, 2, 3, 3, 2, 1] -- you get the idea
  ]

failing: [[Nat]]
failing =
  [
    [1, 2],
    [1, 1, 2],
    ... 
    [1, 1, 1, 1, 2, 2] -- you also get the idea
  ]
```

The signature of `palindrome` as well as a default implementation are required as a minimum for the code and unit tests to compile. 

```haskell
palindrome: [a] -> Boolean
palindrome xs = true
```

Before doing anything else, let's save the scratch file and what `ucm` thinks:
```
⍟ These new definitions are ok to `add`:
    
  failing    : [[Nat]]
  palindrome : [a] -> Boolean
  passing    : [[Nat]]
```

No need to see (or care) about these definitions anymore, and the flow is to `add` them, clear the scratch file, and proceed. 

Note: tests would normally be added under a dedicated namespace. Code organisation is beyond the scope of this post (for now at least).

Suggestion: If you'd rather keep code around it can be converted to comments, for example, and to prevent constant `views`, comment lines out inline by `--` at the beginning of each line, or by adding the comment line: `---`. Anything under `---` is not taken into account by `ucm`.

##### You still haven't written any tests though...

Indeed I have not. I would rather not have to write each test separately, so let's add a quick helper that applies `palindrome` to each member of each list, and aggregates the results to one `Boolean` status.

```haskell
success: ([a] -> Boolean) -> [[a]] -> Boolean
success func inputs =
    foldl (status nextInput -> (func nextInput) && status) true inputs

failure: ([a] -> Boolean) -> [[a]] -> Boolean
failure func inputs =
    foldl (status nextInput -> (func nextInput) || status) false inputs
```

To the above, after removing the [`empty ability symbols`](https://www.unisonweb.org/docs/language-reference/#abilities), for clarity, `ucm` responds with the following :
```
⍟ These new definitions are ok to `add`:
    
  failure : ([a] -> Boolean) -> [[a]] -> Boolean
  success : ([a] -> Boolean) -> [[a]] -> Boolean
```

Once again the flow is to `add` the new definitions, clear the scratch file, and proceed to finally write some test cases! 

##### Tests please!

`palindrome` is [parametric](https://en.wikipedia.org/wiki/Parametric_polymorphism) on type `a`, so for ease of testing, the tests can use `[Nat]`. Writting the tests in the `scratch file`  is straightforward and follows [the guide](https://www.unisonweb.org/docs/tour#testing-your-code).

```haskell
use tests.v1
test> passing.loop = run(expect (success palindrome passing == true))
test> failing.loop = run(expect (failure palindrome failing == false))
```
To the above `ucm` responds:
```
⍟ These new definitions are ok to `add`:
    
  failing.loop : [Result]
  passing.loop : [Result]
   
  4 | test> passing.loop = run(expect (success palindrome passing == true))
    
  ✅ Passed : Passed 1 tests. (cached)
  
  5 | test> failing.loop = run(expect (failure palindrome failing == false))
    
  🚫 FAILED  (cached)
```
The tests (as well as the `success` and `failure` functions) might look attrocious to a more trained eye, but in the spirit of *good enough* and not focusing on testing too heavily, now is a good time to `add`, clear and proceed with implementing `palindrome`.

##### Implement all the things!

The easiest way to implement `palindrome` is to follow the definition of `the input reads the same backward as forward`:

```haskell
palindrome xs = xs == reverse (xs)
```

to which `ucm` will respond:
```
⍟ These new definitions will replace existing ones of the same name and are ok to `update`:
    
   palindrome : [a] -> Boolean
```
Before `updating` the definition of `palindrome`, the second test case is failing, as the original definition is hardcoded:
```
.> test

  Cached test results (`help testcache` to learn more)
  
  ◉ passing.loop    : Passed 1 tests.
  
  ✗ failing.loop   
  
  🚫 1 test(s) failing, ✅ 1 test(s) passing
```
After `updating` the implementation, however, it's a whole new picture:
```
.> update

  ⍟ I've updated to these definitions:
    palindrome : [a] -> base.Boolean

  ✅

.> test

  ✅  

    New test results:
  
  ◉ passing.loop    : Passed 1 tests.
  ◉ failing.loop    : Passed 1 tests.
  
  ✅ 2 test(s) passing
```
Not bad `Unison`, not bad at all. However it gets better:

```
.> test

  Cached test results (`help testcache` to learn more)
  
  ◉ passing.loop    : Passed 1 tests.
  ◉ failing.loop    : Passed 1 tests.
  
  ✅ 2 test(s) passing
```

After updating `palindrome`, the very first invocation of the `test` command actually runs the tests. With the test definitions being `viewable` at any time, subsequent runs will only show cached results. No updates to any code, means no need to run any tests.

##### Could we try another approach?

Let's see what `base.List.halve` does:

```haskell
.> view base.List.halve

  base.List.halve : [a] -> ([a], [a])
  base.List.halve s =
    n =
      use Nat /
      List.size s / 2
    (List.take n s, List.drop n s)
```

The middle index `n` is specified as `s / 2`. This results in  lists of an even number of elements being split to two halves of equal length. However, lists of an odd number of elements will result in the second half being longer by one element.

```
.> 
    ⧩
    ([1], [2, 1])

    ⧩
    ([1, 2], [3, 2, 1])
```

One approach could be: pick the middle element (`2` and `3` in the examples above respectively), push it to the end of the first half, then compare the first half, with the `reverse` of the second half.

##### But it feels a bit brittle...

Debatable, but agreed. A more robust approach might be to implement a slightly different flavour of `halving`, specifically tailored to the needs of `palindrome`. A list of even elements will still be split into two lists of equal length, but in the case of an odd number of elements, the two lists will *both* contain the middle element.

This new version of `halve`, just like in the `base.List` flavour of `halve` will still rely on `base.List.slice`. The intention is to indeed `add` a new function, and not change the `halve` implementation by means of `updating` it.

```haskell
.> view base.List.slice

  base.List.slice : Nat -> Nat -> [a] -> [a]
  base.List.slice start stopExclusive s =
    List.take (Nat.drop stopExclusive start) (List.drop start s)
```

```haskell
halve': [a] -> ([a], [a])
halve' xs =
  s = size xs
  m = s / 2
  if (s `mod` 2 == 1)
  then ((slice 0 (m + 1) xs), (slice m s xs))
  else halve xs

test> halve'.empty = run( expect ( halve' [] == ([], [])))
test> halve'.one = run( expect ( halve' [1] == ([1], [1])))
test> halve'.two = run( expect ( halve' [1, 1] == ([1], [1])))
test> halve'.three = run( expect ( halve' [1, 2, 3] == ([1, 2], [2, 3])))
test> halve'.four = run( expect ( halve' [1, 2, 3, 4] == ([1, 2], [3, 4])))
```

With the new `halve'` and relevant tests `added`, and tests passing, `palindrome` can be reworked. Clearing the scratch file, let's start rewriting `palindrome`:

```haskell
palindrome: [a] -> Boolean
palindrome xs =
  t = halve' xs
  at1 t == (reverse . at2) t
```

```
.> 
  I found and typechecked these definitions in ~/unison/scratch.u. If you do an `add` or `update`,
  here's how your codebase would change:
  
⍟ These new definitions will replace existing ones of the same name and are ok to `update`:
    
   palindrome : [a] -> Boolean
```

Updating the definition and running the tests, the new version does indeed still pass all tests. 

##### And what else?

One could also:
* `zip` the input with its `reverse` and `foldl` over the tuples, is directly equivalent to the original implementation.
* Using `base.List.range`, produce a list of all indexes, `reverse` it then `zip`, to have a list of pairs of elements to be checked for equality. Then access the elements at `(0, n), (1, n - 1), .. (n, 0)` and compare them, at the added cost of having to deal with each access returning `Optional a`. Probably not the easiest or most testable of approaches.
* Compare the first and last element, without the imperative indexing or direct element access, which can be achieved via pattern matching with the help of an inner function:
```haskell
palindrome: [a] -> Boolean
palindrome xs =
  go as bs = case (as, bs) of
    ([], []) -> true
    (head +: tail, init :+ last) -> head == last && go tail init
    (head +: [], [] :+ last) -> head == last
  go xs xs
```

As mentioned in the previous post, `+:` constructs a list from `a head element +: tail list` whereas `:+` constructs a list from `init list :+ the last element`. The above could be coded without `go`, by matching on `xs` twice (`case (xs, xs) of ...`).

##### Are the tests still passing?

Yes they are, and after the initial upfront investment in time and effort, they made up for it by allowing me to:
* have confidence in the continued correctness of `palindrome`
* refactor incrementally, multiple times.

##### And what about all of those famous palindromes?

Well spotted, all yours:
```haskell
use base.Text

test> test.palindromes.greek =
  run( expect( ( (palindrome . toCharList) "ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ") == true))

test> test.palindromes.latin =
  run( expect( ( (palindrome . toCharList) "SATORAREPOTENETOPERAROTAS") == true))

test> test.palindromes.english1 =
  run( expect( ( (palindrome . toCharList) "ablewasiereisawelba") == true))

test> test.palindromes.english2 =
  run( expect( ( (palindrome . toCharList) "amanaplanacanalpanama") == true))

test> test.palindromes.english3 =
  run( expect( ( (palindrome . toCharList) "neveroddoreven") == true))

```

##### Notes!

* A more thorough explanation of how `foldl` works can be found in the [previous post](https://dev.to/petets/an-adventure-in-alpha-testing-3kfn). 
* `success`/`failure` can be very easily written as a single function: take this as an exercise. :wink:
* `unison` also comes with a thorough testing framework which you can locate with `find` and `view` under `base.test.*`. There are probably better ways to aggregate over a number of tests.
* A `delete` `ucm` command can be used to delete no longer needed functions and values from the codebase.
* And as I found out after a very helpful response to my question from [Mitchell Rosen](https://github.com/mitchellwrosen), you can `delete.namespace target.namespace.here` to get rid of all of the tests above for example.
* If it all goes wrong: `undo` is always an option!