As per the previous post in this series, in the process of helping out the community of people
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.
A definition of a
palindrome can be found on Wikipedia.
I previously touched on two
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
test and potentially other
To follow along you will need:
- the Unison codebase manager
ucm. Optionally in the
- A new project created with
ucm -codebase path init.
ucmrunning on your target
ucm -codebase path.
base), cloned (from inside
pull https://github.com/unisonweb/base .base.
- An editor of your choice to open
scratch.u, under the
ucmwill pick up any changes to the
scratch file, and provide output as necessary.
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.
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, 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
⍟ 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
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
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!
use tests.v1 test> passing.loop = run(expect (success palindrome passing == true)) test> failing.loop = run(expect (failure palindrome failing == false))
To the above
⍟ 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
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
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)
ucm will respond:
⍟ These new definitions will replace existing ones of the same name and are ok to `update`: palindrome : [a] -> Boolean
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
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
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
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.
Let's see what
.> 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.
.> ⧩ (, [2, 1]) ⧩ ([1, 2], [3, 2, 1])
One approach could be: pick the middle element (
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.
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
.> 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'  == (, ))) test> halve'.two = run( expect ( halve' [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: [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.
One could also:
zipthe input with its
foldlover the tuples, is directly equivalent to the original implementation.
base.List.range, produce a list of all indexes,
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 ...).
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
- refactor incrementally, multiple times.
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))
- A more thorough explanation of how
foldlworks can be found in the previous post.
failurecan be very easily written as a single function: take this as an exercise. 😉
unisonalso comes with a thorough testing framework which you can locate with
base.test.*. There are probably better ways to aggregate over a number of tests.
ucmcommand 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.hereto get rid of all of the tests above for example.
- If it all goes wrong:
undois always an option!