Working with nested data for algebraic solver

[porkostomus]

I’m starting a project based on the convergence of subjects I’m currently studying. As a high school dropout, I’m desperately trying to make up for the tremendous gaps in my knowledge due to lack of education, particularly in mathematics.

For example, I tried to do some Advent of Code but as soon as math concepts are mentioned that I am unfamiliar with, I immediately feel like I’m not yet ready for this stuff, and ought to be spending my time going back to the fundamentals.

So I’ve been using Khan Academy to learn basic algebra, and since I’m also learning Clojure, have naturally gravitated to using it to assist me in this process, by writing functions to solve the problems for me.

The resulting experience is so delightful that it seems like cheating - but then I realize that by forcing myself to write a program to solve the problem I have actually more thoroughly grasped the concepts, and may have hit upon a very interesting learning path that could be used by others.

I feel like it ought to be developed into some kind of platform for students to learn math and programming (in Clojure, obviously) simultaneously, while opening up opportunities for educational synergy. My vision is to design a Clojure-based computer algebra system in the form of skeleton functions that the student will fill in in order to solve the problem at hand.

I have the first part of it, the infix parser and some basic operations in a live notebook here. I’m very curious to receive some feedback from others on whether I’m going about it the right way, since this is about as naive as it gets. For example, the parsed equation comes in the form of nested vectors:

user=> (equation "1+x=65")
([:left [:number "1"] "+" [:variable "x"]] [:right [:number "65"]])

Say I just want to extract the 1 on the left. What I have so far works, but feels really awkward:

(defn left [s]
  (rest (first (equation s))))

(defn right [s]
  (rest (last (equation s))))

(defn left-num [s]
  (cond
    (= :number (first (first (left s))))
    (Integer/parseInt (last (first (left s))))
    (= :number (first (last (left s))))
    (Integer/parseInt (last (last (left s))))
    :else nil))

user=> (left-num "1+x=65")
1

How do people normally deal with nested vectors like this? Should I use something like specter? Or am I missing a much more idiomatic way to do this with another library or just the core? Since I’m already using instaparse to reduce the parsing job to nearly nil, it just looks odd to see the work involved in un-parsing it so disproportionally verbose. But more importantly, it totally obscures what’s going on… just looks like a mess of firsts, lasts, etc.

Thank you for your feedback!

[PEZ]

I’ll be following this. I’m looking for a fun way to let my 9yo son explore algebra. Dragon Box is fun, but this would allow us to experiment much more. And then learn some programming while at it!

About the dealing with the parse tree. Zippers come to mind.

[porkostomus]

It gets really fun when we get into graphing stuff. In Nextjournal, we have access to all sorts of charts with plotly:
https://nextjournal.com/btowers/using-plotly-with-clojure/

[daslu]

Great idea, looking forward to see that platform you are planning!

It may be a good idea to try implementing it in cljc, so that everything may run at the browser, too. Then, one may rely on Klipse or maria.cloud for the interactive platform for students.

In case you haven’t seen those, here are some existing libraries in this area of computational algebra:

Sophia-Gold/symbolic-algebra

clojure-numerics/expresso

Maybe they may come in handy.

Yes, specter is really nice for this kind of situations, in my opinion.

And yes, that mess of firsts and lasts can be quite an obstacle for readability.

Sometimes, it helps to be more verbose and name the parts of your nested structures through destructuring.

So, in your example:

user> (def eq1
  [[:left [:number "1"] "+" [:variable "x"]] [:right [:number "65"]]])
#'user/eq1
user> (defn left [eq]
        (rest (first eq)))
#'user/left
user> (left eq1)
([:number "1"] "+" [:variable "x"])
user> (defn verbose-left [[[_ & left-hand-side] [_ & right-hand-side]]]
        left-hand-side)
#'user/verbose-left
user> (verbose-left eq1)
([:number "1"] "+" [:variable "x"])
user> 

[jackrusher]

What you probably want here is to build a recursive evaluator than works on arbitrary trees rather than something specialized to a single example tree.

[jackrusher]

As an example of what I mean, here’s a simple evaluator for a parsed infix tree:

(defn evaluate [expr]
  (condp = (first expr)
    :number (Integer/parseInt (second expr))
    :variable (second expr)
    (if (string? expr) 
      ({"+" + ":" - "/" / "*" *} expr) ; is an operator
      (first (reduce (fn [[v op] op-or-value]
                       (if (fn? op-or-value)
                         [v op-or-value]
                         [(op v op-or-value) op]))
                     [0 +]
                     (map evaluate expr))))))

(evaluate [[:number "20"] "+" [:number "20"] "/" [[:number "2"] "+" [:number "2"] "+" [:number "4"]]])
;;=> 5

… which scales to arbitrary subexpression depth and doesn’t require manual destructuring.

Note that I’ve assumed you will not pass :left and :right markers at the head of your two parsed sequences, as they add only the difficulties of non-uniformity to your situation and you can identity them positionally. The above evaluator will fail if you pass it an expression containing a variable, which I’ve left as a simple exercise.

[porkostomus]

I see, that make a lot of sense. It anticipates the next move, which will be larger and more complex expressions. Thanks!

[didibus]

Ya, I think for just accessing or updating an element in a nested structure specter is great. For navigating thorough it, I think Zippers could be used clojure.zip, but I’ve never used zipper myself though. Some people also use lenses libraries like spectacles and traversy, but I don’t think they’re quite as mature as specter.

But for what you seem to be trying to do, people normally treat the vector as a Tree, and perform some sort of tree traversal over it to perform evaluation. Either over a parse tree or an abstract syntax tree.

This article helped me understand the difference between the two https://ruslanspivak.com/lsbasi-part7/

[rmcv]

Yes it is a mess to unparse but you can always use pattern matching to simplify it - e.g. https://stackoverflow.com/a/54687183/6013799