I'm trying to solve this SICP exercise using clojure with core/match and core/typed.
I'm kind of following Jeanine Adkisson's "Variants are Not Unions" talk.
This is what I got so far:
(ns sicp.chapter2_ex29
(:require [clojure.core.typed :as t]
[clojure.core.match :refer [match]]))
; Type definitions
(t/defalias Mobile '{:left Branch, :right Branch})
(t/defalias Weight Number)
(t/defalias Structure
(t/U '[(t/Value :weight) Weight]
'[(t/Value :mobile) Mobile]))
(t/defalias Branch '{:length Number, :structure Structure})
; Constructors
(t/ann make-mobile [Branch Branch -> Mobile])
(defn make-mobile [left right]
{:left left :right right})
(t/ann make-branch [Number Structure -> Branch])
(defn make-branch [length structure]
{:length length :structure structure})
; Getters
(t/ann left-branch [Mobile -> Branch])
(defn left-branch [mobile]
(:left mobile))
(t/ann right-branch [Mobile -> Branch])
(defn right-branch [mobile]
(:right mobile))
(t/ann branch-length [Branch -> Number])
(defn branch-length [branch]
(:length branch))
(t/ann branch-structure [Branch -> Structure])
(defn branch-structure [branch]
(:structure branch))
; Total weight
(t/ann total-weight [Mobile -> Number])
(defn total-weight [mobile]
(t/letfn> [structure-weight :- [Structure -> Number]
(structure-weight [structure]
(do
(println (str "structure -> " structure))
(println (str "structure0 -> " (get structure 0)))
(println (str "structure1 -> " (get structure 1)))
(match structure
[:weight weight] weight
[:mobile mobile] (total-weight mobile))))
branch-weight :- [Branch -> Number]
(branch-weight [branch]
(structure-weight (branch-structure branch)))]
(let
[left (branch-weight (left-branch mobile))
right (branch-weight (right-branch mobile))]
(do
(println (str "left ->" left))
(println (str "right ->" right))
(+ left right)))))
(t/ann mobile1 Mobile)
(def mobile1 (make-mobile
(make-branch 3 [:weight 4])
(make-branch 5 [:weight 2])))
(total-weight mobile1) ; <- works as expected = 6
(t/ann mobile2 Mobile)
(def mobile2 (make-mobile
(make-branch 3 [:weight 4])
(make-branch 5 [:mobile (make-mobile
(make-branch 2 [:weight 3])
(make-branch 4 [:weight 2]))])))
(total-weight mobile2) ; <- throws java.lang.IllegalArgumentException: No matching clause: [:mobile {:left {:length 2, :structure [:weight 3]}, :right {:length 4, :structure [:weight 2]}}]
The Structure type is a variant: either it is a weight, which is simply a number (it has the form [:weight weight] where weight is a Number) or it is a mobile (it has the form [:mobile mobile] where mobile is something of type Mobile).
It type-checks and the total-weight function works for a simple input: a Mobile made of two Weights.
But as you can see it fails for a Mobile with a Branch that is a Mobile.
For some reason it isn't matching the [:mobile mobile] case. Any idea on what am I doing wrong?
The problem appears to be that the identifier mobile
in
(match structure
[:weight weight] weight
[:mobile mobile] (total-weight mobile))))
... is already bound as an argument in the enclosing function definition:
(defn total-weight [mobile]
... )
Changing the match
form to
(match structure
[:weight w] w
[:mobile m] (total-weight m))))
... removes the error.
The rule appears to be:
If a name in a
match
pattern is bound, it is not rebound locally. It is interpreted as its prevailing value.
I have to say I only found the error by accident. I would prefer that the local binding took precedence, but it doesn't.
Notes
The syntax of your match
expression does not follow the documentation, which would require ...
(match [structure]
[[:weight w]] w
[[:mobile m]] (total-weight m))
... but your abbreviated version works just as well.
The Clojure idiom is to use standard data structures - especially maps - where possible, eschewing access functions and constructors. In this way, we can write something like
; Total weight
(declare structure-weight)
(t/ann total-weight [Mobile -> Number])
(defn total-weight [mobile]
(match [mobile]
[{:left bl, :right br}]
(apply + (map
(comp structure-weight :structure)
[bl br]))))
(t/ann structure-weight [Structure -> Number])
(defn structure-weight [structure]
(match [structure]
[[:weight w]] w
[[:mobile m]] (total-weight m)))