Clojurians Log v2

@madarauchiha: are you still looking at the infix->prefix question?

I looked at this question, because I’d just done something like it recently

I’m guessing you’re in a timezone that won’t see this until later, so I’ll dump in here for now

I’ll confess that there may well be a much better way (and when I did it myself I used parsatron, so I was already doing it differently)

but this is how I did it...

first of all, I wanted to test for operators at each level. * and / have the same precedence, as do + and -

Also, I’m going to presume symbols, so my test expression will be similar to yours:

(def test-expression '(1 + 2 * 3 - 4 * 5 + 6))

if I simplify for a moment… let’s just look at the * operator:

(def test2 '(a * b * c * d))

to get to this, we want to group (1 + 2) as a, (3 - 4) as b, etc ARGH! I did this back to front! It still works but I need to invert everything that follows! Please bear this in mind as you read!!!! I’ll fix this at the end, promise!!! 😳

a function for that is split-with. The test to use is anything that’s not a * or /. That can be done by complementing the set: (def mtest (complement '#{* /}))

testing it on the expression:

=> (split-with mtest test-expression)
[(1 + 2) (* 3 - 4 * 5 + 6)]

decent start. So now let’s loop to split it all up. We’ll want to pull those operators out too, so I’ll use some destructuring to get at it, and the remainder:

(loop [result [] ex test-expression]
  (let [[next-operand [op & remaining]] (split-with mtest ex)
        new-result (conj result next-operand)]
    (if op
      (recur (conj new-result op) remaining)
      new-result)))

[(1 + 2) * (3 - 4) * (5 + 6)]

this let us split by the * character! For anyone watching… maybe there was an easier way?

anyway, this was useful. It also looks like something we could use to split by the + and - characters. So I can wrap it in a function and parameterize on that

(defn factor-out [the-test expression]
  (loop [result [] ex expression]
    (let [[next-operand [op & remaining]] (split-with the-test ex)
          new-result (conj result next-operand)]
      (if op
        (recur (conj new-result op) remaining)
        new-result))))

and a new test function for summation-type operators: (def stest (complement '#{+ -}))

so, now I have a way to take an expression and pull it down into the form '(a op b op c). So now we want to process it into (op a (op b c))

remember, I said they start as binary operators, so that means whenever we see '(a op ….) then we’re going to turn that into '(op a …) If we don’t see an op (i.e. just have a single thing like '(a) then we just want to return that

I’m going to recurse this time...

because it looks like a general rule

if we pull out the first item, the operator, and the remainder, then when there is a remainder still to be processed, we return a list of the operator, the first item and then everything else processed. When there is no remainder to be processed (the operator should be nil in this case) then just return that first item

(defn prefix-form [[item op & remainder]]
  (if (seq remainder)
    (list op item (prefix-form remainder))
    item))

how did this go? Trying it out:

=> (prefix-form (factor-out mtest test-expression))
(* (1 + 2) (* (3 - 4) (5 + 6)))

Great! So now we just want to do pretty much the same thing to the +- expressions

Let’s take the first one… '(1 + 2)

=> (factor-out stest '(1 + 2))
[(1) + (2)]

this is pretty good, but what about the parens around the 1 and 2?

Turns out, they’re OK. The reason is clearer if we think about operands in the general sense. If we look at a language that supports ^ for raising to a power, then this has higher precedence than */ which has higher precedence than +-

basically, we want to apply our method at each level of precedence, and then do it again with new tests each time

OK, at the point where I will try to invert everything 😳

let’s try again...

=> (prefix-form (factor-out stest test-expression))
(+ (1) (- (2 * 3) (+ (4 * 5) (6))))

the precedence is fixed, and it’s all still working. This is what abstraction does for us 😄

So I got things backwards, but abstracting meant it was a trivial bug 🙂

each element in the prefix form (the things being added and subtracted) now just need to be operated on in the same way, except with */ instead of +-

so… let’s re-write prefix-form, this time taking a function saying what we want to do with the elements that show up as arguments:

(defn prefix-form-better [f [item op & remainder]]
  (if (seq remainder)
    (list op (f item) (prefix-form remainder))
    (f item)))

if f=identity then it’s exactly what we had a moment ago

Let me read it all, one moment 😄

OK… I have just 2 lines of code to the final solution now 🙂 (and they’re really simple lines)

What does this mean?

Complement of a set?

do you know how a set is a function?

That's news to me.

I knew it was an iterable

it can be used as a truthy/falsey test

I see

there are a number of functions that can take advantage of it

So a set is also a predicate that accepts an argument and returns whether or not that argument is in the set

exactly

I see

So complement will return the predicate which returns true when the argument isn't in the set

Gotcha

if I try: (map #{3} [1 2 3 4 5]) I get back [nil nil 3 nil nil]

So you can do things like (filter set1 set2) to get the intersection

yes 🙂

Neat

Alright back to reading

complement changes a truthiness test into a true/false test

Yeah, I know what complement does

cool

I wrote my own before learning about it 😄

Then I thought "wait, there's no way a functional language doesn't already have complement, I'm an idiot"

OK… I’ll just finish…

if we look at the final steps first… evaluating things like ((2) * (3)) can be done by calling prefix-form-better using identity, and we get:

(prefix-form-better identity '((2) * (3)))
(* (2) (3))

since we have this handy function that we’re applying, then instead of identity, we can use first

define that to be a function, and it can be the “f” that gets passed in to make the prefix-sum!

(def prefix-prod #(prefix-form-better first (factor-out mtest %)))
(def prefix-sum #(prefix-form-better prefix-prod (factor-out stest %)))

yes, I did. I did it in my own repl using functions that had single character names 🙂

so when I did a copy/paste to Slack, I had to correct manually. Sometimes I stuffed up 🙂

This is another thing I wanted to ask, because I'm unfamiliar with how developing in a Lispy language works

Do you generally write code in the repl, and then copy it to a file?

Do you write the code in the file, load it in repl, then play with it? How do you persist the work from the REPL afterwards?

most people do it in emacs or another editor that lets you apply read/eval to parts of the buffer

that typically involves a learning curve on how to do it. It doesn’t take long, but it can be annoying

if you’ve use a CLI repl, then I open the history file and use that 🙂

anyway…. I have to go

I hope I didn’t write at too simple a level for you. You were away and couldn’t ask questions, so I figured I should explain it to the simplest level that I could think of

That's fine, it's really helpful

Thanks a lot for your time!

I also apologize for getting the precedence wrong. No idea what I was thinking there! I think it’s very cool that it just involved a little bit of swapping of symbols and it worked again 🙂

you’re welcome on the time. Hopefully someone will offer a better solution than this one

to be complete… this is the working code I used:

(defn fp [t exp]
  (loop [r [] ex exp]                     
    (let [[n [op & rem]] (split-with t ex)
          newr (conj r n)]
      (if op                              
        (recur (conj newr op) rem)        
        newr))))

(defn prefix [f [l op & r]] (if (seq r) (list op (f l) (prefix f r)) (f l)))

(def stest (complement '#{+ -}))
(def mtest (complement '#{* /}))
(def prefix-prod #(prefix first (fp mtest %)))
(def prefix-sum #(prefix prefix-prod (fp stest %)))

(prefix-sum ‘(1 + 2 * 3 - 4 * 5 + 6))

Hmm

I think the result is wrong though 😛

user=> (prefix-sum '(1 + 2 * 3 - 4 * 5 + 6))
(+ 1 (- (* 2 3) (+ (* 4 5) 6)))

That should be something like

(+ 1 (+ (- (* 2 3) (* 4 5)) 6))