Palindromes

Disclaimer

As per the previous post in this series, in the process of helping out the community of people alphatesting the Unison programming language, I am solving the 99 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 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. 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, 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 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? Let's begin by adding a number of lists some being and some not being palindromes.

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.

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.

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, 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 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.

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:

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:

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

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

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:

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:

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:

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.
• success/failure can be very easily written as a single function: take this as an exercise. 😉
• 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, 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!