Forem: Pete Tsamouris

Unison.IO

Pete Tsamouris — Mon, 17 Feb 2020 15:00:44 +0000

Before we begin!

Quick reminder that Unison is still in public alpha!

Parts of the language, testing functionality and libraries that appear in this post might be subject to change.

In the following post I will do my best to refer to command-line user input and output as I/O when in free text mode, which also seems to be the preferred term of the Unison documentation and guide. In code snippets, the ability will be referred to as IO with the base.io. namespace omitted for brevity.

Problem statement: I/O operations in Unison.

I will try and frame the problem statement as a BDD scenario:

GIVEN An individual interested in the Unison PL
WHEN  That individual investigates I/O
THEN  They have an brief document available to guide them

I will concede at this point that the real problem statement is:

GIVEN I have done I/O before on numerous occasions
WHEN  I need to remind myself yet again how to do it
THEN  I have my notes kept somewhere

😇 and 🤦‍♀️

Do I need to understand abilities in depth to do I/O?

Strictly speaking: to get acquainted with I/O you will have to get acquainted with abilities.

If all you care to do is at this point is "read some input from the console and write some output to it" an in depth understanding of what abilities are or how they are handled internally is strictly not necessary. I have however helpfully added the documentation link for your convenience, as some familiarity with the syntax and the moving parts is necessary.

How does `ucm` run a program?

Let's have a quick look at an excerpt of the output of the ucm help command:

$ ucm help

...
  ucm run .mylib.mymain
  Executes the definition `.mylib.mymain` from the codebase, then exits.

  ucm run.file foo.u mymain
  Executes the definition called `mymain` in `foo.u`, then exits.
...

ucm can be asked to run an existing codebase definition if pointed to an entity via its full namespace path. Furthermore the run.file flag type-checks the file ucm is pointed to and then runs the existing codebase definition.

At the time of writing for ucm to run an entity it must have a type of '{ IO } ()

So single ticks and curly braces?

It might look strange at first but abilities amongst other things are meant to allow "the same syntax for programs that do (asynchronous) I/O", to quote the documentation. In other languages you might see a signature like:

f : Int => Unit for a synchronous function
f : Int => IO [Unit] for a function that performs IO

One could observe that "sure IO involves input and output" but is that synchronous or asynchronous?

By using abilities and handlers the requirement for asynchronous context during the steps in the body of f would be expressed as:

f: Int -> {e} () (e being the empty set of abilities)
f: Int -> {IO} () (still synchronous but involves I/O)
f: Int -> '{IO} () (asynchronous and involves I/O)

While trying to not stray and discuss abilities in general, for the strict scope of I/O the last remaining bit to explain is the single tick. It denotes a delayed computation which is the Unison way of doing asynchronous computations.

How can I get `IO` (the Unison ability) in my codebase ?

At the time of writing IO comes as part of the ucm base package that can be pulled while running ucm.

.> pull https://github.com/unisonweb/base .base

And what can `IO` do ?

A complete list of what IO can do can be found by means of looking under base.io. The focus for a simple input-manipulate-output program will be the two functions that allow reading and writing to the console:

base.io.readLine : '{IO} Text
base.io.printLine : Text ->{IO} ()

So how that documentation example?

use io

program : '{IO} ()
program = 'let
  printLine "What is your name?"
  name = !readLine
  printLine ("Hello, " ++ name)

the function is declared as a delayed side effect '{IO} ()
the body must begin with a "delayed let"
delayed calls must be forced with ! in this instance !readLine

It might seem a bit heavy to digest in one go but what you have at this point is a program that performs I/O by using the mechanics of the IO ability. The syntax is such that functions that require synchronous IO are called directly whereas functions that require asynchronous IO are forced (at the "end of the world" when the I/O is handled by the runtime).

Run it!

Copy paste the code into scratch.u
add the program function as an entity in your codebase (its namespace will be . by default, so it will live under .program)

Followed by one of these commands:

ucm run.file scratch.u program

ucm run .program

The output will be something along these lines:

$ ucm run .program

What is your name?
X 
Hello, X

Packing consecutive list elements

Pete Tsamouris — Wed, 05 Feb 2020 17:13:51 +0000

Before we begin!

Quick reminder that Unison is still in public alpha!

Parts of the language, testing functionality and libraries that appear in this post might be subject to change.

Exercise 9: Pack consecutive duplicates into sublists

The aim of the pack function is to take a list of type [a] and group all consecutive duplicate elements into sublists, the output type being [[a]]. At the same time, the unpack function reverses the packing the aim being to allow for better ease of testing (more on this below) .

Please note the use of the term sublist for every list embedded in the outer list, for example in [[1], [2, 2], [3]] each of [1], [2, 2] and [3] will be referred to as a sublist.

How will we know we have built the right thing?

Let's consider pack first:

An empty list still needs to return a [[a]] (yet technically [] and [[]] both type-check against [[a]]).
Any single element list [x] will be wrapped in a list to form a sublist: [[x]]
Generalising the previous property: a list of non duplicate elements will end up with each element wrapped in a single element list.
The minimum list containing a duplicate element [x, x] will see the elements wrapped in a single sublist: [[x, x]]
So in the most general case any list consisting of consecutive duplicate and non consecutive duplicate elements will end up with sublists where length > 1, as well as sublists where length == 1.

Let's now have a look at unpack:

Any list containing an empty list ([[]]) will unpack to [].
Consecutive sublists, regardless of the number of elements in each, will be concatenated to a flattened list.

From a property based perspective:

For any not packed list U the length of U will be equal to the sum of the lengths of the sublists that are contained in the packed list P, where pack U produces P.
Any list L that can be packed to a list P can subsequently be unpacked to a resulting list L' with the two lists L == L' being equal.

On testing:

Having recently been made aware of the check and check' test helpers I will be making use of them to write my unit and property tests from now on.

For reference the tour (for the time being!) only mentions expect and run (expect (...)) but the check and check' functions can also be used to yield slightly more concise test cases.

Let's write some tests then!

Lets add the signatures of pack and unpack and implement a minimum hard coded and clearly wrong version, only to allow the compiler to run the tests.

use .base

pack : [a] -> [[a]]
pack as = []

unpack : [[a]] -> [a]
unpack aa = []

Here are the unit tests for pack:

test> test.pack.empty = 
  check (pack [] == [])

test> test.pack.single = 
  check (pack [1] == [[1]])

test> test.pack.duplicate = 
  check (pack [1, 1] == [[1, 1]])

test> test.pack.list = 
  check (pack [1, 2, 2, 3, 4, 4] == [[1], [2, 2], [3], [4, 4]])

And here are the unit tests for unpack:

test> test.unpack.empty = 
  check (unpack [[]] == [])

test> test.unpack.empty' = 
  check (unpack [] == [])

test> test.unpack.single = 
  check (unpack [[1]] == [1])

test> test.unpack.duplicate = 
  check (unpack [[1, 1]] == [1, 1])

test> test.unpack.list = 
  check (unpack [[1], [2, 2], [3], [4, 4]] == [1, 2, 2, 3, 4, 4])

Repetitive much?

You might have noticed a ...slight repetition in the testing department. I am allowing a slight peek in the test-case-writing-process on purpose to better highlight why property tests might be helpful in this instance. Since the pack and unpack methods take us from [a] to [[a]] and back again, instead of testing pack with a set of inputs and outputs then unpack with the set of outputs as inputs it is (usually) quicker to test both at the same time using the approach sometimes referred to as there and back again.

A quick find for generators under base.v1.test reveals that a small number of additional generators would come handy in our case to allow freedom to better shape the test inputs to our needs.

Originally I wrote a non empty list generator (inspired from the stock list generator, with the range being always a minimum two elements) as well as a consecutive elements list generator, that when forced produces a list containing exclusively consecutive elements.

base.test.v1.non_empty_list : '{Gen} a -> '{Gen} [a]
base.test.v1.non_empty_list g =
  'let
    size = !nat
    List.map (_ -> !g) (range 1 (size + 2))

base.test.v1.consecutive_list: '{Gen} a -> '{Gen} [a]
base.test.v1.consecutive_list g = 
  ' let
      size = increment (!nat)
      elem = !g
      List.map (_ -> elem) (range 1 (size + 2))

Then I noticed the lack of reuse between the two functions as well as general lack of information being communicated at the type level and most importantly, at this point the codebase contains 3 more or less identical functions for list, with slightly different arguments.

Slight detour to use a non empty list type for the above, by making use of Unison record types:

type NonEmptyList a = { head' : a, tail' : [a]}

toList : NonEmptyList a -> [a]
toList nel = case nel of
  NonEmptyList.NonEmptyList hd tl -> [hd] ++ tl

base.test.v1.nel : '{Gen} a -> '{Gen} (NonEmptyList a)
base.test.v1.nel g = 'let NonEmptyList !g !(list g) 

base.test.v1.consecutive_nel : '{Gen} a -> '{Gen} (NonEmptyList a)
base.test.v1.consecutive_nel g = 
  'let 
    non_empty = !(nel g)
    hd = head' non_empty
    NonEmptyList (hd) ([hd] ++ tail' non_empty)

So a consecutive_nel is produced in terms of a nel, while head' is added to the scope by Unison by the definition of the record type members head' and tail'.

base.test.v1.unpacked_list: '{Gen} [Nat]
base.test.v1.unpacked_list =
  'let
    large = pick ['((!nat) + 10), '((!nat) + 100)]
    small = pick ['((!nat) + 1), '((!nat) + 10)]
    s1 = !(nel large)
    m1 = !(consecutive_nel small)
    join (map toList [m1, s1, m1, s1])

Is this overly complex? Maybe, but I would like to be able to produce input-lists for my tests containing clearly discernible elements so I can be sure to notice if I break the generator.

> sample 100 '(!unpacked_list)
   ⧩
   [ [1, 1, 10, 1, 1, 10],
     [1, 1, 10, 10, 10, 10],
     [10, 10, 10, 1, 1, 10],
     [10, 10, 10, 10, 10, 10],
     [1, 1, 10, 1, 1, 100],
     [1, 1, 10, 10, 10, 100],
     [10, 10, 10, 1, 1, 100],
     ...
     truncated

Note: '(!(list nat)) produces some lists with consecutive values due to the nature and behaviour of the nat generator, but this behaviour cannot be relied upon. The {Gen} ability handlers are not random number generators but rather domain enumerators in specific order and the same holds for how pick selects a generator from the list too.

So what about the properties then?

In order to minimise the code and since all property tests are meant to test the same properties mentioned already (length of sub-lists equal to the unpacked list, unpack . pack produces the input), it is handy to write a test generator that given a generator for a list of some structure, checks if the properties hold over a number of iterations tested.

use base.Nat +
use base.Nat map

subListLengths: [[a]] -> Nat
subListLengths aas = foldl (+) 0 (map size aas)

test : '{Gen} [a] -> '{Gen} Test
test generator = 
  'let
    l = !(generator)
    packed = pack l
    unpacked = unpack packed
    check' ((unpacked == l) && (subListLengths packed == size unpacked))

test> test.pack_unpack.empty = 
  check (((unpack . pack) []) == [])

test> test.pack_unpack.list =
  runs 100 (test (list nat))

test> test.pack_unpack.consecutive = 
  runs 100 (test unpacked_list)

Caveat: runs 100 (test (list nat)) probably has more brackets than I care to write. It also took a number of attempts to get it to type-check, but I suppose this will get more intuitive given time and practice.

After a day spent writing tests, could we "pack" a list maybe?

In the past I have attempted my best to implement the function that is the main focus of the exercise in as many ways as possible. In this instance I feel that there are only so many ways that are worthwhile, and some of them rely on (currently) missing standard library functions. I will only implement pack in terms of takeWhile and dropWhile (which I have unit tested previously, and are beyond our scope at this point):

base.List.dropWhile : (a -> Boolean) -> [a] -> [a]
base.List.dropWhile pred as =
  case as of
    []              -> []
    h +: t | pred h -> dropWhile pred t
    _               -> as

base.List.takeWhile : (a -> Boolean) -> [a] -> [a]
base.List.takeWhile pred as =
  case as of
    []              -> []
    h +: t | pred h -> [h] ++ takeWhile pred t
    h +: _          -> []

pack : [a] -> [[a]]
pack as = case as of
  []  -> []
  h +: t -> (h +: (takeWhile (e -> e == h) t)) +: pack (dropWhile (e -> e == h) as)

unpack : [[a]] ->[a]
unpack = join

It helps that unpack is actually provided for free with the Unison base library. In case you don't have it immediately handy to check the implementation, here's how you can concatenate a list containing sublists into a flat list:

.> view base.List.join

  base.List.join : [[a]] -> [a]
  base.List.join =
    use List ++
    foldl (++) []

But are the tests and properties passing?

Why don't we find out:

.> test

  ✅

    New test results:

  ◉ test.pack.empty                 : Proved.
  ◉ test.pack.single                : Proved.
  ◉ test.pack.duplicate             : Proved.
  ◉ test.pack.list                  : Proved.

  ◉ test.unpack.empty               : Proved.
  ◉ test.unpack.empty'              : Proved.
  ◉ test.unpack.single              : Proved.
  ◉ test.unpack.list                : Proved.

  ◉ test.pack_unpack.empty          : Proved.
  ◉ test.pack_unpack.list           : Proved.
  ◉ test.unpack.duplicate           : Proved.
  ◉ test.pack_unpack.consecutive    : Proved.


  ✅ 12 test(s) passing

  Tip: Use view test.pack_unpack.empty to view the source of a
       test.

Turns out yes they are, so that's a wrap!

Property based testing in Unison

Pete Tsamouris — Tue, 21 Jan 2020 18:01:05 +0000

Property testing in Unison

Quick reminder that Unison is still in public alpha!

Parts of the language, testing functionality and libraries that appear in this post might be subject to change.

On properties

There are a lot of very good resources on property testing out there with some pointing to a number of different approaches.

Depending on whom you ask and what your current level of familiarity is, identifying properties of the code being delivered may fall under the "easier said than done" column. I will use the compress function from my previous blog post "Eliminate consecutive duplicates" to try and highlight what the process might look like.

This post is meant to help the reader explore:

property based testing as a concept and practice.
the Unison programming language.
just how easy it is to write property tests in Unison.

Remind me about `compress` real quick?

Being parametric on type a when given an input-list [a] compress will remove consecutive elements in the list, if any exist. Do not be afraid of some level of formality: for two lists [1, 2, 3] and [1, 1, 1], the former would be classed as non compressible, whereas the latter would be classed as compressible. The result of the compression being the output-list [1].

In the previous blog post I implemented compress in multiple ways and here's the one I want to test using property tests.

base.List.compress: [a] -> [a]
base.List.compress as = case as of
  [] -> []
  [x] -> [x]
  [x, y] ++ rest ->
    if (x == y) then base.List.compress (y +: rest)
    else x +: base.List.compress (y +: rest)

What will be our testing criterion?

In the following section, C denotes a compressible list, and U a list that cannot be compressed. A list is compressible if after compress is applied to it, the output-list contains less elements than the input.

This is an arbitrarily picked criterion and different criteria could be selected, hence why I called it "our" criterion. Another criterion might be that an input-list U would be equal to the output-list U.

What are (some of) the properties of `compress`?

Non compressible list properties

The minimum U list is the empty list.
Any list [x] (containing a single element) is equally not compressible.
U ++[x] will be non compressible, for any value x as long as x is not equal to the last element.
The above can be generalised so that U ++ U will be compressible if the head and tail of U are the same element.
Inversely: removing elements one at a time from a U list and finally reaching the point of the empty list, produces a sequence of U lists.

Compressible list properties

For each element x, the list [x, x] is the minimum non empty C list.
The above can be generalised in two ways:
- The U list containing head +: tail can be converted to a C list by means of the operation [head, head] ++ tail.
- The U list containing init :+ last can be converted to a C list by means of the operation init ++ [last, last].
Unrelated to the cornercase above, C ++ [x] will be compressible, for any value x regardless of whether x is equal to the last element of C or not (as the compressible section does not need to be in the end).
Generalising the above: C ++ U is compressible, just like U ++ C is compressible, just like C ++ C is compressible.
U ++ U will be compressible if the head and tail of U are the same element.

Whether a list can be compressed or not is all about content. As long as the equal consecutive elements are always one next to the other, a class of list manipulation operations like reversing will not affect the ability of the list to compress or not.

The lists of properties above might not necessarily be exhaustive but we have more than a few to work with. Note that properties are a mathematical concept so there is a certain degree of lack of formal notation and formal definition in the section above, as well as some leaps in logic that might not hold water from a strict mathematical perspective. The focus of this post however is not math, but Unison.

Now what about `Unison` specifically?

The relevant section of the documentation can be found in the Unison tour. Please follow the link and have a read!

Here is a step by step breakdown of what the pieces involved:

A use .base.test.v1 statement.
Each line that declares a property test must begin with test>.
The test> expression is followed by the name of the test this "path" reflects the namespace under which the test will be added.
The property itself, as in the content of the go function.
A call to the runs function specifying how many times to run which test, in the example, 100 go

I know that the addition of natural numbers is associative!

And here is one way to prove that the natural number addition assosiative property holds in Unison:

use builtin.Nat +

test> tests.base.Nat.associative = 
  go _ = a = !nat
         b = !nat
         c = !nat
         expect (((a + b) + c) == (a + (b + c)))
  runs 100 go

What just happened?

There is a Unison syntax guide that is part of the tour:

ucm had a hard time time finding out which of all the functions called + the code was referring to, so it was guided to pick the one for natural numbers by the use statement.
The delayed ability to generate a natural number (nat) was forced with the exclamation mark syntax (!nat).
Which means that the nat function, for each call, produced one natural number.
The expect function was used to test the property.
The property was expressed as a boolean equality check.
The go function and contained code block is the test, and it ignores its first argument _.
Ignoring the first argument is the mechanism in Unison to make a function lazy (caveat: if my understanding of the documentation is correct).
The aptly named runs function is what actually "runs" the "property" 100 times.

What building blocks does Unison provide?

Unison comes with generators that are exposed by the Gen ability under the base.test.v1 namespace to produce values of given types. We can build on top of the nat and list (generator and function respectively) to craft genetators and functions that produce lists of that are known to meet certain criteria, for use in property tests. The generators are not random (as I originally thought).

.> view base.test.v1.nat

  base.test.v1.nat : '{Gen} Nat
  base.test.v1.nat = '(Gen.sample Weighted.nats)

.> view base.test.v1.list

  base.test.v1.list : '{Gen} a -> '{Gen} [a]
  base.test.v1.list g =
    'let
      size = !nat
      List.map (_ -> !g) (range 0 size)

The Gen ability is handled by the Unison test runtime. The how exactly is beyond our scope at this time. If you are not fully familiar with abilities, they are covered in the documentation.

What is the test-predicate function?

The predicate functionchecks if after compression an output-list contains less elements than the input-list. To make the tests a bit more readable the compression is hidden inside the predicate.

should_compress: [a] -> Boolean
should_compress as = (size . compress) as < size as

should_not_compress: [a] -> Boolean
should_not_compress = not . should_compress

Compressible generators

To benefit from compositionality begin by coding a generator that produces a minimum compressible list (the content of which could be randomised). This generator can then be peppered on to other lists to make any otherwise non compressible list always compressible.

base.test.v1.min_compressible : '{Gen} a -> '{Gen} [a]
base.test.v1.min_compressible g =
  'let
    x = !g
    [x, x]

min_compressible gets passed an argument g that is a delayed generator of type a. The generator is forced to produce a value with !g

base.test.v1.compressible : '{Gen} a -> '{Gen} [a]
base.test.v1.compressible g =
  'let
    !(min_compressible g) ++ !(list g)

Syntactically, same as above, !(min_compressible g) forces min_compressible to return a minimum compressible list, the content of which is produced by the generator g, and !(list g) does the same, except the list produced by !(list g) is not structured.

Non compressible generators

Having a second look at the base.test.v1.list list generator, there is no guarantee that consecutive calls of the g generator that it reuses for the value of each element, will not yield the same value twice.

Furthermore g is passed as an argument so without an in depth understanding of how g could behaved the list generator is bound to always produce unexpected results for a whole class of generators like a constant generator that always produces a fixed value.

Narrowing the scope for natural numbers only, here is one way to produce a non compressible list.

base.test.v1.non_compressible : '{Gen} [Nat]
base.test.v1.non_compressible =
  'let
    start = !nat
    size  = !nat
    List.map (i -> start + i) (range 0 size)

The list begins with a natural number and all numbers after it are sequenced after incrementing so there can be no consecutive duplicates. But, there is no guarantee that consecutive calls of this generator will not end up producing lists that when concatenated are compressible, for example [1, 2, 3] and [3]. To avoid this we would need to code a generator that produces two lists at the same time, to ensure their content cannot be compressed when appended (beyond the scope of this blog).

Let's write some properties then!

The minimum non compressible list is the empty list

test> tests.compress.emptyIsNotCompressible = 
  go _ = expect (should_not_compress [])
  runs 1 go

In a language where there would be a need to import a unit test library and a separate property test library, one might be tempted to code a simple unit test as a property test of a single run, to save the time and energy of dealing with multiple test libraries. In this instance and at this point in time in the evolution of Unison: it does not really matter. The test result is cached regardless.

Every list of a single element is non compressible

test> tests.compress.singleElement = 
  go _ = expect (should_not_compress [!nat])
  runs 1 go

Every non compressible list can be sequentially deconstructed to non compressible lists

recurse: ([a] -> Boolean) -> [a] -> Boolean
recurse pred as = 
  pred as && case (as, as) of 
    (_ +: t, i :+ _) -> recurse pred t && recurse pred i
    ([], []) -> pred []

test> tests.compress.decomposeU = 
  go _ = l = !(non_compressible)
         expect (recurse should_not_compress l)
  runs 100 go

A non compressible list appended to a non compressible list is compressible under some circumstances

test> tests.compress.uAppendU = 
  go _ = a = !(non_compressible)
         b = !(non_compressible)
         lambda = case (a, b) of
           (_ :+ l, h +: _) -> 
             if h == l then should_compress else should_not_compress
            _ -> should_not_compress
         expect (should_not_compress a 
           && should_not_compress b && lambda (a ++ b) )
  runs 100 go

Every non empty minimum compressible list can be compressed

test> tests.compress.minimumCompressible = 
  go _ = expect (should_compress !(min_compressible nat))
  runs 100 go

Every compressible list appended to a non compressible list results in a compressible list

test> tests.compress.cAppendU = 
  go _ = a = !(min_compressible nat)
         b = !non_compressible
         expect (should_compress a && should_not_compress b && should_compress (a ++ b))
  runs 100 go

Every non compressible list appended to a compressible list results in a compressible list

test> tests.compress.uAppendC = 
  go _ = a = !non_compressible
         b = !(min_compressible nat)
         expect (should_compress (a ++ b))
  runs 100 go

Every compressible list appended to a compressible list results in a compressible list

test> tests.compress.cAppendC = 
  go _ = a = !(min_compressible nat)
         b = !(min_compressible nat)
         expect (should_compress (a ++ b))
  runs 100 go

Every compressible list extended by an element is still compressible

test> tests.compress.extendC = 
  go _ = a = !(compressible nat)
         b = !nat
         expect (should_compress a && should_compress (a ++ [b]))
  runs 100 go

Closing note

I hope I have managed to communicate in this post just how easy and pleasant it is to work with Unison when it comes to property based testing.

Eliminate consecutive duplicates

Pete Tsamouris — Sat, 11 Jan 2020 18:10:00 +0000

Disclaimer

As per the previous posts in this series, in the process of helping out the community 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 faste, more obvious or easier approach is readily available.

Understanding of some concepts of functional programming might be required and the intention of this series is to be tailored to a beginner-level audience. For all concepts mentioned in the post I have made the effort to embed relevant hyperlinks. In the event you encounter something you don't fully understand, but does come with a hyperlink-hint feel free to either read to the end then search, or why not get a quick glimpse of the term before you proceed.

Exercise 8: Eliminate consecutive duplicates of list elements.

Can I play too?

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 your project under codebase by means of: 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 codebase: ucm will tell you the folder in which it will pick up any changes to the scratch file, and provide output as necessary.

So how do we know this thing will work?

Why don't we write some tests first. The function we are trying to write will be called compress by convention and will reduce a list of elements to a list of maybe less elements. It can directly be placed in the base.List namespace, by adding the path to the namespace before the definition, but that is not necessary.

base.List.compress: [a] -> [a]
base.List.compress as = []

test> tests.compress.empty =
  run ( expect ( base.List.compress [] == [] ))

test> tests.compress.nonCompressable1 =
  run ( expect ( base.List.compress [1] == [1] ))

test> tests.compress.nonCompressable2 =
  run ( expect ( base.List.compress [1, 2] == [1, 2] ))

test> tests.compress.nonCompressable3 =
  run ( expect ( base.List.compress [1, 2, 3] == [1, 2, 3] ))

test> tests.compress.compressable1 =
  run ( expect ( base.List.compress [1, 1, 1, 2, 2, 3] == [1, 2, 3] ))

test> tests.compress.compressable2 =
  run ( expect ( base.List.compress [1, 2, 2, 3] == [1, 2, 3] ))

test> tests.compress.compressable3 =
  run ( expect ( base.List.compress [1, 1] == [1] ))

test> tests.compress.example =
  run(
    expect(
      (base.List.compress [?a, ?a, ?a, ?a, ?b, ?c, ?c, ?a, ?a, ?d, ?e, ?e, ?e, ?e] ==
       [?a, ?b, ?c, ?a, ?d, ?e])
    )
  )

Note: compress is directly coded into the base.List namespace above, and all tests point to it by full path. This is equivalent to first using the cd .base.List command, to move namespace, then coding compress without a namespace in the declaration and implementation.

  I found and typechecked these definitions in :scratch.u. If
  you do an `add` or `update`, here's how your codebase would
  change:

    ⍟ These new definitions are ok to `add`:

      base.List.compress              : [a] -> [a]
      tests.compress.compressable1    : [Result]
      tests.compress.compressable2    : [Result]
      tests.compress.compressable3    : [Result]
      tests.compress.empty            : [Result]
      tests.compress.example          : [Result]
      tests.compress.nonCompressable1 : [Result]
      tests.compress.nonCompressable2 : [Result]
      tests.compress.nonCompressable3 : [Result]

  Now evaluating any watch expressions (lines starting with
  `>`)... Ctrl+C cancels.

    5 |   run ( expect ( base.List.compress [] == [] ))

    ✅ Passed : Passed 1 tests.

    8 |   run ( expect ( base.List.compress [1] == [1] ))

    🚫 FAILED 

    11 |   run ( expect ( base.List.compress [1, 2] == [1, 2] ))

    🚫 FAILED 

    14 |   run ( expect ( base.List.compress [1, 2, 3] == [1, 2, 3] ))

    🚫 FAILED 

    17 |   run ( expect ( base.List.compress [1, 1, 1, 2, 2, 3] == [1, 2, 3] ))

    🚫 FAILED 

    20 |   run ( expect ( base.List.compress [1, 2, 2, 3] == [1, 2, 3] ))

    🚫 FAILED 

    23 |   run ( expect ( base.List.compress [1, 1] == [1] ))

    🚫 FAILED 

    26 |   run(

    🚫 FAILED

The test cases above contain the following inputs:

the empty list []
a non compressible list containing one, two and three elements
a compressible list beginning with a compressible sequence, and containing a compressible sequence afterwards
a compressible list beginning with a non compressible sequence, followed by a compressible one
the example from the problem definition, which on closer scrutiny and in good humour almost provides more coverage than the previous cases put together.

So what next?

ucm agrees with the types and syntax so far so we can add these definitions, and clear the scratch file.

.> add

  ⍟ I've added these definitions:

    base.List.compress              : [a] -> [a]
    tests.compress.compressable1    : [Result]
    tests.compress.compressable2    : [Result]
    tests.compress.compressable3    : [Result]
    tests.compress.empty            : [Result]
    tests.compress.example          : [Result]
    tests.compress.nonCompressable1 : [Result]
    tests.compress.nonCompressable2 : [Result]
    tests.compress.nonCompressable3 : [Result]

So can we now implement `compress`?

Let's have a first try, while relying on list look-ahead. Previously I would view a definition on the terminal and then copy-paste that into the scratch file. I will from now on use the edit command, so that ucm will do this for me.

base.List.compress: [a] -> [a]
base.List.compress as = case as of
  [] -> []
  [x] -> [x]
  [x, y] ++ rest ->
    if (x == y) then base.List.compress (y +: rest)
    else x +: base.List.compress (y +: rest)

  I found and typechecked these definitions in :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`:

      base.List.compress : [a] -> [a]

  Now evaluating any watch expressions (lines starting with
  `>`)... Ctrl+C cancels.

If the input is the empty list there is nothing to be done and compress returns the empty list. Alternatively the (x +: (y +: rest)) clause matches on a list of at least two elements, so it can proceed to check these two elements. If they are equal y is a duplicate of x, and the next function call will have input of y +: rest so as not to completely discard the x|y element. If they are not equal, x is not discarded and equally y is not discarded either. Notice that I jumped ahead to a list of two elements: there is a remaining clause to be matched which I am also adding at this time: [x] -> [x]. A list containing a single element, just like the empty list, is left intact.

My first take of the function above, give or take some minor attempts to get the syntax right, was using the pattern (x +: (y +: rest)) to refer to a list of at least two elements. After a comment by Paul Chiusano, turns out the same can be coded as [x, y] ++ rest, which saves some bracket noise.

.> update

  ⍟ I've updated to these definitions:

    base.List.compress : [a] -> [a]

  ✅

  No conflicts or edits in progress.

.> test

  ✅  

    New test results:

  ◉ tests.compress.compressable1       : Passed 1 tests.
  ◉ tests.compress.compressable3       : Passed 1 tests.
  ◉ tests.compress.compressable2       : Passed 1 tests.
  ◉ tests.compress.example             : Passed 1 tests.
  ◉ tests.compress.nonCompressable2    : Passed 1 tests.
  ◉ tests.compress.nonCompressable3    : Passed 1 tests.
  ◉ tests.compress.nonCompressable1    : Passed 1 tests.
  ◉ tests.compress.empty               : Passed 1 tests.

  ✅ 8 test(s) passing

  Tip: Use view tests.compress.compressable1 to view the source
       of a test.

With the function under test updated the tests have "new results". Note however that running the test command again does not rerun any tests, but shows cached tests results, as long as the function under test has not been updated since the last run.

So can we do another one? With less pattern matching?

There might be quite a few alternatives worth exploring and we can begin by looking into an iterative approach using foldl.

First a reminder of the signature and implementation of foldl:

.> view base.List.foldl

  base.List.foldl : (b ->{𝕖} a ->{𝕖} b) -> b -> [a] ->{𝕖} b
  base.List.foldl f b as =
    go b i =
      case List.at i as of
        None -> b
        Some a ->
          use Nat +
          go (f b a) (i + 1)
    go b 0

Going over each element of the list while using an accumulator, if the last element encountered matches the current element then it can be discarded, otherwise this element is appended to the accumulator and will be the basis of comparison in the next iteration.

base.List.compress: [a] -> [a]
base.List.compress as = 
  f acc elem = case acc of
    [] -> [elem]
    (init :+ last) -> if (last == elem) then acc else (acc :+ elem)
  foldl f [] as

  I found and typechecked these definitions in :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`:

      base.List.compress : [a] -> [a]

  Now evaluating any watch expressions (lines starting with
  `>`)... Ctrl+C cancels.

After updating compress, tests are still passing.

.> test

  ✅  

    New test results:

  ◉ tests.compress.example             : Passed 1 tests.
  ◉ tests.compress.empty               : Passed 1 tests.
  ◉ tests.compress.nonCompressable3    : Passed 1 tests.
  ◉ tests.compress.compressable3       : Passed 1 tests.
  ◉ tests.compress.nonCompressable2    : Passed 1 tests.
  ◉ tests.compress.nonCompressable1    : Passed 1 tests.
  ◉ tests.compress.compressable2       : Passed 1 tests.
  ◉ tests.compress.compressable1       : Passed 1 tests.

  ✅ 8 test(s) passing

  Tip: Use view tests.compress.example to view the source of a
       test.

Are there more alternative approaches?

Yes there are: one using dropWhile (not part of the Unison base library yet) and one using group (also not part of base yet).

Care to go ahead regardless?

Using "dropWhile"

There are probably multiple ways to implement dropWhile or in other words a function that given a predicate, will keep dropping elements from the head of the list for as long as the predicate holds. For example:

dropWhile (x -> x < 3) [1, 2, 3, 4, 1, 2] -> [3, 4, 1, 2]

The straightforward way is to just implement it as per its definition, without relying on an abstraction.

base.List.dropWhile: (a -> Boolean) -> [a] -> [a]
base.List.dropWhile pred as =
  case as of
    [] -> []
    h +: t ->
      if pred h then dropWhile pred t
      else as


  I found and typechecked these definitions in :scratch.u. If
  you do an `add` or `update`, here's how your codebase would
  change:

    ⍟ These new definitions are ok to `add`:

      dropWhile : (a ->{𝕖} Boolean) ->{𝕖} [a] ->{𝕖} [a]

  Now evaluating any watch expressions (lines starting with
  `>`)... Ctrl+C cancels.

For dropWhile the predicate is tested and if it is false there are no items to drop. On the other hand if it is true then the head is dropped and dropWhile recurses into the remaining elements of the tail, using the same mechanism.

So finally compress can be implemented in terms of dropWhile as follows:

base.List.compress: [a] -> [a]
base.List.compress as = 
  case as of
    [] -> []
    h +: t -> 
      dropped = dropWhile (x -> x == h) t
      h +: compress dropped

  I found and typechecked these definitions in :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`:

      base.List.compress : [a] -> [a]

  Now evaluating any watch expressions (lines starting with
  `>`)... Ctrl+C cancels.

In this version compress firstly acts as a means of breaking the list down to the head +: tail clause, which then allows the remaining elements of tail to be checked for equality with head and dropped if matching. Once dropWhile finishes filtering after the current head compress recurses into the remaining elements of the dropped intermediate result list.

.> update

  ⍟ I've updated to these definitions:

    base.List.compress : [a] -> [a]

  ✅

  No conflicts or edits in progress.

.> test

  ✅  

    New test results:

  ◉ tests.compress.nonCompressable1    : Passed 1 tests.
  ◉ tests.compress.compressable3       : Passed 1 tests.
  ◉ tests.compress.nonCompressable2    : Passed 1 tests.
  ◉ tests.compress.compressable1       : Passed 1 tests.
  ◉ tests.compress.empty               : Passed 1 tests.
  ◉ tests.compress.nonCompressable3    : Passed 1 tests.
  ◉ tests.compress.example             : Passed 1 tests.
  ◉ tests.compress.compressable2       : Passed 1 tests.

  ✅ 8 test(s) passing

  Tip: Use view tests.compress.nonCompressable1 to view the
       source of a test.

Using "group"

Feel free to experiment with this one which I will describe but not code. Given a function that "groups" same elements into lists, you can run group on the input and end up with a list of lists of same elements. Collecting the head of each of those lists will give you a neat solution.

(For those who are a bit more advanced, or curious for more detail, group could be implemented in terms of groupBy (spoiler here), which in turn could be implemented in terms of span (spoiler here))

Thanks for reading!

Note:

A great many thanks to Daniel Skinner for reviewing and commenting the original draft of this post.

Make your blogs run!

Pete Tsamouris — Sun, 05 Jan 2020 18:05:17 +0000

Unison comes with a convenient way of reproducing user interactions with ucm for all intents and purposes.

Originally not aware of transcripts, I started writing the odd Unison blog the hard way, that is, text in one location, code snippets and output being copy-pasted. The 1980s way of doing things worked out for a lot of people after all. Turns out, if you're working with markdown to begin, graduation to transcripts is not that far off.

So what are `unison transcripts`?

Transcripts are markdown files with a twist. They mix in blocks of Unison code, to be typechecked by ucm, and blocks of commands, to be run by ucm.

The input-transcript can be orchestrated in such a way that markdown text as well as unison and ucm blocks are interleaved to produce output that is ready for consumption by third parties.

What are the pros?

As mentioned, you can formulate your interaction with ucm in a detailed and documented manner, with comments and explanations to pinpoint specifically for example what the exact requirements are to reproduce a bug or failure.

No time wasted explaining, just share the transcript, which in effect acts as an integration test. If something is wrong with ucm, a fix followed by a passing run means the fix holds. (And the unison code base does indeed follow this approach currently).

Being markdown files, you can use your editor of choice, and the formatting rules you are (potentially) already familiar with.

What are the cons?

Depending on the circumstances, certain aspects of reproducing a whole environment (beginning with a couple of heavy git pulls for example) might mean that the process can become slow and maybe bloated.

If your main aim is to share code in general, transcripts cannot replace a code repository.

Also, each transcript runs in its own sandbox, so cleanup of the sandboxed checkouts will be required afterwards.

How does it work in practice?

ucm outputs the regular markdown of the transcript directly to the output file, until it finds specific fenced blocks (as per the example that follows). These blocks are translated as ucm commands (pull from github, test, add, update and all the usual suspects), or unison code to be typechecked.

ucm blocks containing commands are issued to a sandboxed ucm and unison blocks are typechecked in the same sandbox for correctness. You can emulate the unison blocks to run in the context of a specific file.

Can I play too?

All you need is:

the Unison codebase manager ucm. Optionally in the $PATH.
an editor of your choice edit the transcript in.

You need be able to run ucm and point it to a transcript. Name the transcript example.md, and when ready, run: ucm transcript example.md.

Where do we start?

A number of examples come with the Unison codebase, hello being the one I used as a guide.

For the curious: you might want to look into what happens during the stack exec tests build step when compiling Unison from source.

What is a "minimum viable transcript"?

Technically, an empty markdown file, although that would not really be of much use to you. So here's an example of content that contains a unison and a ucm block.

```unison
str = "hello"
```

Once the above block is typechecked, a ucm block can issue commands that operate on the previous code block.

```ucm
.> add
.> view str
.> undo
```

To sum up: a transcript with the above two blocks will create a sandboxed checkout, then typecheck the unison block, then run the ucm commands.

Here is the output of ucm after processing the transcript successfully.

ucm transcript example.md

  Transcript will be run on a new, empty codebase.

  ⚠️

  Initializing a new codebase in:
  /.../transcript-75f55eaeebee4386

   _____     _             
  |  |  |___|_|___ ___ ___ 
  |  |  |   | |_ -| . |   |
  |_____|_|_|_|___|___|_|_|

  Running the provided transcript file...


⚙️   Processing stanza 2 of 2.
💾  Wrote /.../unison/example.output.md

  🌸

  I've finished running the transcript(s) in this codebase:

    /.../transcript-75f55eaeebee4386

  You can run
  `ucm -codebase /.../transcript-75f55eaeebee4386`
  to do more work with it.

ucm even provides you with the next command to run, in order to continue interactively, from where the transcript concluded.

Hope you find transcripts useful!

Thanks!

I must at this point thank Arya Irani, for reviewing this post for syntax, grammar and spelling errors.

Nested list flattening

Pete Tsamouris — Wed, 01 Jan 2020 16:35:38 +0000

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.

Understanding of some concepts of functional programming might be required, and the intention of this series is to be tailored to a beginner-level audience. For all concepts mentioned in the post, I have made the effort to embed relevant hyperlinks, so in the event you encounter something you don't fully understand, feel free to either read to the end then search, or why not get a quick glimpse before you proceed.

Exercise 7: Flatten a nested list structure

Can I play too?

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.

Wait, `nested` lists are a thing?

Unison does support user defined types, and these will be the focus of this post.

Consider the following definition, where the nested structure is abstracted behind a single type signature:

type Nested a = Element a | List [Nested a]

Instances of the Nested type, can contain:

a single element of type a, or
a list of elements of this type, as noted by [Nested a]

Element and List are the two constructors of the algebraic data type Nested.

And it's as easy as that?

Let's ask ucm:

⍟ These new definitions are ok to `add`:

  type Nested a

  Now evaluating any watch expressions (lines starting with `>`)... Ctrl+C cancels.

To give the semblance of uniformity with the rest of the Unison data types, I will cd base before adding the type to the codebase. You can be reminded of the constructors' signatures by using ls:

.> ls .base.Nested

  1. Element (a -> Nested a)
  2. List    ([Nested a] -> Nested a)

So what about tests?

We begin by adding the signature of the flatten method, with a default implementation, to be able to write unit tests.

The nested list does encode structure in it, so I will try and cover as many types of structure in my tests:

flatten: Nested a -> [a]
flatten any = []

test> tests.flatten.empty = 
  run( expect( flatten ( List []) == []))
test> tests.flatten.elem  = 
  run( expect( flatten ( Element 1) == [1]))
test> tests.flatten.elems =
  run( expect( flatten ( List [Element 1, Element 2]) == [1, 2]))
test> tests.flatten.nestOne =
  run( expect( flatten ( List [ List[Element 1]]) == [1]))
test> tests.flatten.nestedMany =
  run
    (expect
      (   flatten
           (List
             [ Element 1,
               List [List [Element 2, List [Element 3]]],
               Element 4 ])
      == [1, 2, 3, 4]))

Here are the scenarios tested:

Empty List
Single Element
List containing multiple Element values
List inside a List, containing an Element
Element followed by List, followed by List followed by Element

The above could have been broken down to simpler, more granular test cases, but I find that this is quickly becoming tedious, and does not really offer much additional value to you, the reader. By all means, feel free to experiment with more granular test cases. The last one overlaps in coverage with the third and fourth.

ucm agrees with the types of the above, and runs the tests, all of which, except the first one, are of course failing (omitted for brevity).

⍟ These new definitions are ok to `add`:

  flatten                  : Nested a -> [a]
  tests.flatten.elem       : [Result]
  tests.flatten.elems      : [Result]
  tests.flatten.empty      : [Result]
  tests.flatten.nestOne    : [Result]
  tests.flatten.nestedMany : [Result]

Can we now fill in the implementation of `flatten`?

Let's by all means. Here's one way to go about it:

flatten: Nested a -> [a]
flatten e =
  case e of
    Element el -> [el]
    List (l +: ls) -> flatten l ++ flatten (List ls)
    List [] -> []

If flatten encounters an Element, which only wraps a single el, all it needs to do is wrap it in a list. If it encounters a List of any structure of nested values, it breaks it in head +: tail, and separately recurses into head and tail, concatenating the two calculated results with (++). This approach uses simple recursion.

⍟ These new definitions will replace existing ones of the same name and are ok to `update`:

  flatten : Nested a -> [a]

⍟ I've updated to these definitions:

  flatten : .Nested a -> [a]

After the update, tests are passing!

  ◉ tests.flatten.empty            : Passed 1 tests.
  ◉ tests.flatten.elem             : Passed 1 tests.
  ◉ tests.flatten.nestOne          : Passed 1 tests.
  ◉ tests.flatten.elems            : Passed 1 tests.
  ◉ tests.flatten.nestedMany       : Passed 1 tests.

Can we `generalise` the recursion?

As mentioned in the first post of this series, since the original flatten is using simple recursion, it can be expressed in terms of foldb.

flatten: Nested a -> [a]
flatten e =
  case e of
    Element el -> [el]
    List l -> foldb (flatten) (++) [] l

As a reminder, here is the foldb signature (find/view), along with the type signatures, as well as orchestration to implement flatten, layed out one by one.

.> view base.List.foldb
  base.List.foldb : (a -> b) -> (b -> b -> b) -> b -> [a] -> b
  base.List.foldb f op z as

(Nested a -> [a]) ->                             flatten
([a] -> [a] -> [a]) ->                           (++) 
[a] ->                                           [] 
[Nested a] ->                                    l

foldb starts (and ends prematurely if the input is empty), with []. Whenever it encounters a component of [Nested a] (beginning with the head of l), it runs the f function, in this case flatten. It then concatenates (++) the output of op a with the previously accumulated result.

After an update, the tests are still passing.

Can the `recursion/foldb` be turned into an `iteration`?

By relying on a small helper function, the last implementatoin can be expressed in differently formulated manner that avoids foldb.

First, consider the following signature, where f can turn a value of a to a number of values of [b]:

f: a -> [b]

f can be passed to a function that, for the sake of uniformity with Haskell, will be called concatMap. concatMap then iterates over the [a] and converts each instance to a [b].

I will at this point make a quick detour, and add tests for concatMap: I rely on it to implement flatten, so for the sake of thoroughness, it should be functioning as expected:

test> tests.concatMap.empty =
  run (expect (concatMap (a -> [a]) [] == []))
tests.concatMap.idOne =
  run (expect (concatMap (a -> [a]) [1] == [1]))
tests.concatMap.doubleOne =
  run (expect (concatMap (a -> [a, a]) [1] == [1, 1]))

These tests pass, and prove that concatMap indeed only applies f to each a in the list, without performing any additional transformations. Feel free to be more thorough, but in the confines of Unison, the type signatures can be trusted.

Going back to the task at hand, for our purposes f is flatten, and a -> [b] is Nested a -> [a]

concatMap: (a -> [b]) -> [a] -> [b]
concatMap f as = foldl (acc a -> acc ++ f a) [] as

flatten: Nested a -> [a]
flatten e =
  case e of
    Element el -> [el]
    List ls -> concatMap flatten ls

As before, if flatten encounters an Element, the a -> [a] conversion is a "wrap in a list" operation. When it encounters a [Nested a], flatten does not recurse into itself by calling itself. Instead it calls concatMap that uses flatten as the function to work with. Internally, concatMap runs foldl.

⍟ These new definitions will replace existing ones of the same name and are ok to `update`:

  flatten : Nested a -> [a]
.> update

⍟ I've updated to these definitions:

  flatten : Nested a -> [a]

With tests passing, that's a wrap!

Palindromes

Pete Tsamouris — Sat, 28 Dec 2019 13:42:45 +0000

Disclaimer

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!

Find the last element of a list

Pete Tsamouris — Wed, 18 Dec 2019 17:37:23 +0000

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

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

Forem: Pete Tsamouris

Unison.IO

Before we begin!

Problem statement: I/O operations in Unison.

Do I need to understand abilities in depth to do I/O?

How does ucm run a program?

So single ticks and curly braces?

How can I get IO (the Unison ability) in my codebase ?

And what can IO do ?

So how that documentation example?

Run it!

Packing consecutive list elements

Before we begin!

Exercise 9: Pack consecutive duplicates into sublists

How will we know we have built the right thing?

On testing:

Let's write some tests then!

Repetitive much?

So what about the properties then?

After a day spent writing tests, could we "pack" a list maybe?

But are the tests and properties passing?

Property based testing in Unison

Property testing in Unison

On properties

Remind me about compress real quick?

What will be our testing criterion?

What are (some of) the properties of compress?

Non compressible list properties

Compressible list properties

Now what about Unison specifically?

I know that the addition of natural numbers is associative!

What just happened?

What building blocks does Unison provide?

What is the test-predicate function?

Compressible generators

Non compressible generators

Let's write some properties then!

The minimum non compressible list is the empty list

Every list of a single element is non compressible

Every non compressible list can be sequentially deconstructed to non compressible lists

A non compressible list appended to a non compressible list is compressible under some circumstances

Every non empty minimum compressible list can be compressed

Every compressible list appended to a non compressible list results in a compressible list

Every non compressible list appended to a compressible list results in a compressible list

Every compressible list appended to a compressible list results in a compressible list

Every compressible list extended by an element is still compressible

Closing note

Eliminate consecutive duplicates

Disclaimer

Exercise 8: Eliminate consecutive duplicates of list elements.

Can I play too?

So how do we know this thing will work?

So what next?

So can we now implement compress?

So can we do another one? With less pattern matching?

Are there more alternative approaches?

Care to go ahead regardless?

Using "dropWhile"

Using "group"

Note:

Make your blogs run!

So what are unison transcripts?

What are the pros?

What are the cons?

How does it work in practice?

Can I play too?

Where do we start?

What is a "minimum viable transcript"?

Thanks!

Nested list flattening

Disclaimer

Exercise 7: Flatten a nested list structure

Can I play too?

Wait, nested lists are a thing?

And it's as easy as that?

So what about tests?

Can we now fill in the implementation of flatten?

Can we generalise the recursion?

Can the recursion/foldb be turned into an iteration?

Palindromes

How does `ucm` run a program?

How can I get `IO` (the Unison ability) in my codebase ?

And what can `IO` do ?

Remind me about `compress` real quick?

What are (some of) the properties of `compress`?

Now what about `Unison` specifically?

So can we now implement `compress`?

So what are `unison transcripts`?

Wait, `nested` lists are a thing?

Can we now fill in the implementation of `flatten`?

Can we `generalise` the recursion?

Can the `recursion/foldb` be turned into an `iteration`?

Simple recursion using `uncons`

I think there's more in `base.List`

The `unison` way!