Oct 11, 2017 - Contatiners Redux

Comments

Another bite

We're only going to look at one more function from the Containers core protocol, flat-map. I'll leave the others until I can introduce some more data types to illustrate their use.

The flat-map protocol function is probably the single most useful of all the core protocol functions. What does it do? Glad you asked.

Suppose we wanted to see if the first element of a list of numbers was equal to 15. First, we need to get the first element of the list

  (first (list 15 99 24))
  => <maybe 15>

(The => is just short hand for 'produces:'. Toccata doesn't have a REPL that you can type these expressions into yet. Look in the examples directory for some short programs to run.)

So first returns a Maybe value that has the first element in it. So far, the way we've seen to reach inside a Maybe value is with the map function.

  (map (first (list 15 99 24))
       (fn [x]
         (= 15 x)))
  => <maybe <maybe 15>>

That's not right. What we need is a function similar to map that will apply a given function to the value inside a Maybe value and then remove one layer of wrapping (or 'flatten') the result. flat-map to the rescue.

  (flat-map (first (list 15 99 24))
            (fn [x]
              (= 15 x)))
  => <maybe 15>

But what happens when the list is empty and first returns a nothing value? Exactly what you'd expect.

  (flat-map (first (list))
            (fn [x]
              (= 15 x)))
  => nothing

And finally, what if the head of the list isn't 15?

  (flat-map (first (list 1 2 3))
            (fn [x]
              (= 15 x)))
  => nothing

And now, with lists!

How does flat-map work with lists? Pretty straightforward. First regular map.

  (map (list 15 99 24)
       (fn [x]
         (list (inc x))))
  => ((16), (100), (25))

Nothing too surprising, I hope. And now flat-map

  (flat-map (list 15 99 24)
            (fn [x]
              (list (inc x))))
  => (16, 100, 25)

And for completeness, flat-map on an empty list

  (flat-map (list)
            (fn [x]
              (list (inc x))))
  => ()

also, if the result of the given function is an empty list

  (flat-map (list 1 2 3)
            (fn [x]
              (list)))
  => ()

for!

If you're a Clojure programmer, you might have thought about Clojure's for expression for sequence comprehension.

  (for [x (list 15 99 24)]
    (inc x))
  => (16, 100, 25)

Toccata has the exact same expression. It is another example of a special form that could be a macro. The above expression gets expanded to

  (let [#arg (list 15 99 24)]
    (flat-map #arg (fn [#x]
                     (wrap #arg (inc #x)))))

So for is written in terms of wrap and flat-map. But that also means that, in Toccata for works for any data type that implements those function. Like Maybe

  (for [head (first (list 15 99 24))]
    (inc head))
  => <maybe 16>

This is a huge thing in Toccata and we'll eventually spend a lot more time looking at this.

Oct 10, 2017 - Containers

Comments

Our story so far ...

So far, we've looked at several of the protocols at the heart of Toccata. I chose to build Toccata on top of these protocols because of one word; Abstraction. A lot of smart people have said a lot of good things about the value of abstraction. I won't add to that here except to say that having single name for a concept that's applicable across many kinds of data is a good thing. It helps newcomers get up to speed more quickly and gives authors of libraries a framework to fit their ideas into.

Now it's now time to dig into the big daddy of the core protocols.

Containers

This protocol describes functionality for data types that contain other values, similar to Collection. However, the focus here is more on the containing value rather than the contents.

Describing all this will probably take 2 or 3 posts. So let's get to it.

  (defprotocol Container
    (map [x f])
    (wrap [x v])
    (apply* [xf xs])
    (flatten [x])
    (flat-map [x f])
    (extend [x f])
    (extract [x])
    (duplicate [x])
    (send* [x f-and-ys]))

map

This function creates a new container value of the same type as x by calling f with each value contained in x and gathering the results in the new container.

People familiar with Clojure will notice some differences here. First, map can be defined for any data type, not just sequences. Second, the value being mapped over comes first, and the function comes second. (The reverse of Clojure's map function.) Third, it can only ever map over one container value where Clojure zips a number of sequences together and then calls the mapping function. To get similar functionality in Toccata, you'll need to zip the sequences before calling map.

But most importantly, you can map over all kinds of values, not just sequences.

  (main [_]
    (println "map nothing:" (map nothing inc))

    (println "map (maybe 8) with inc:" (map (maybe 8) inc)))

If you then compile and execute this program (perhaps using the run script from the repo), you get this output.

  map nothing: <nothing>
  map (maybe 8) with inc: <maybe 9>

So you can see that trying to map the nothing value will not execute the mapping function and just returns nothing. While mapping any other Maybe value, will apply the function to the contents.

The fact that map implementations should always return values of the same type as the first argument is important.

  (main [_]
    (println "map vector:" (map [1 2 3] inc)))

produces

  map vector: [2, 3, 4]

This is one of the things Nathan Marz addressed in his Specter library for Clojure.

wrap

This produces a new container of the same type as x but with only the value v inside it. wrap is not used directly that often. Presumably, any place you'd call wrap, you'd just call the value constructor directly. However, it is used in code the compiler generates, so it should be defined for types that implement other functions from the Container protocol.

apply*

This requires some explanation. When you write a call like this:

  (apply f x y z)

it gets rewritten by the compiler to:

  (apply* f (list x y z))

This should be a macro, but Toccata doesn't have macros yet, so it's a special form. In this case, f could be a plain function and then apply is just the same as Clojure's apply and z should be a list of values. But if f is wrapped in a container of some sort:

  (apply (maybe +) (maybe 3) (maybe 4))

Then they all get unwrapped before the function is applied to the arguments, so the above expression produces <maybe 7>.

There's another special form called apply-to.

  (apply-to + (maybe 3) (maybe 4))

which gets expanded to

  (let [#x (maybe 3)]
    (apply* (wrap #x +) #x (maybe 4)))

This also evaluates to <maybe 7>. Where it get's interesting is when you do something a little more complicated.

  (apply-to + (= 0 x) (maybe 4))

In this contrived expression, only if x is 0 will 4 be added to it. This is equivalent to

  (map (= 0 x) (fn [x]
                  (+ 4 x)))

And now, Vectors

Hopefully, seeing this with Maybe values is pretty clear. But what happens when the container is little more complicated? Several examples should illustrate without too much commentary.

  (apply-to inc [])
  produces: []

  (apply-to inc [1 2 3])
  produces: [2 3 4]

  (apply-to list [1 2 3] [10 30])
  produces: [(1 10) (2 10) (3 10) (1 30) (2 30) (3 30)]

  (apply-to + [1 2 3] [10 30])
  produces: [11 12 13 31 32 33]

  (apply-to + [1 2 3] [] [10 20 30])
  produces: []

Oct 9, 2017 - Associative

Comments

One more very quick post before we get to the meat of the core library.

Associative

  (defprotocol Associative
    (assoc [m k v])
    (get [m k])
    (keys [m])
    (vals [m]))

The hash-map, under various names, is probably one of the most used data structures currently in use. Being able to associate a pair of values is hugely useful. You could probably make the argument that there's something fundemental there. Toccata specifies the Associative protocol to capture this abstraction so it can be applied more widely.

assoc

Establish a mapping between a key value k and value v in the collection m. Returns a new collection while m remains unchanged. The new collection is of the same type as m.

get

Retrieve the value associated with k from m. Since such an association may not exist in m, Implementations of this protocol must return a value of type Maybe (nothing or a Maybe value containing a value).

keys

Return a (possibly empty) list of the keys in m.

vals

Return a (possible empty) list of the values in m.

Next time

These last 3 posts cover most of the core Toccata protocols and should be pretty familiar for most programmers. The remaining one is the Container protocol. It's not really anymore difficult, but it is more abstract. So next time, we're going to change direction and start looking at concrete examples of Toccata code as we explore one aspect of what really sets Toccata apart.