Fork me on GitHub
#braveandtrue
<
2016-09-12
>
quoll17:09:24

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

quoll19:09:25

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

quoll19:09:08

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

quoll19:09:22

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)

quoll19:09:30

but this is how I did it...

quoll19:09:02

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

quoll19:09:57

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

quoll19:09:37

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

quoll19:09:52

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

quoll19:09:34

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

quoll19:09:58

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

quoll19:09:08

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 '#{* /}))

quoll19:09:37

testing it on the expression:

quoll19:09:17

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

quoll19:09:21

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:

quoll19:09:43

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

quoll19:09:46

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

quoll19:09:19

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

quoll19:09:25

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

quoll19:09:46

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

quoll19:09:36

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

quoll19:09:04

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

quoll20:09:01

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

quoll20:09:14

I’m going to recurse this time...

quoll20:09:23

because it looks like a general rule

quoll20:09:30

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

quoll20:09:02

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

quoll20:09:52

how did this go? Trying it out:

quoll20:09:58

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

quoll20:09:37

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

quoll20:09:21

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

quoll20:09:55

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

quoll20:09:19

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

quoll20:09:27

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

quoll20:09:25

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

quoll20:09:47

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

quoll20:09:07

let’s try again...

quoll20:09:32

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

quoll20:09:09

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

quoll20:09:07

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

quoll20:09:27

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

quoll20:09:19

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:

quoll20:09:39

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

quoll20:09:26

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

Madara Uchiha20:09:09

Let me read it all, one moment 😄

quoll20:09:30

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

Madara Uchiha20:09:43

What does this mean?

Madara Uchiha20:09:56

Complement of a set?

quoll20:09:23

do you know how a set is a function?

Madara Uchiha20:09:30

That's news to me.

Madara Uchiha20:09:42

I knew it was an iterable

quoll20:09:47

it can be used as a truthy/falsey test

quoll20:09:08

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

Madara Uchiha20:09:14

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

Madara Uchiha20:09:44

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

quoll20:09:04

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

Madara Uchiha20:09:51

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

Madara Uchiha20:09:56

Alright back to reading

quoll20:09:59

complement changes a truthiness test into a true/false test

Madara Uchiha20:09:07

Yeah, I know what complement does

Madara Uchiha20:09:17

I wrote my own before learning about it 😄

Madara Uchiha20:09:45

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

quoll20:09:12

OK… I’ll just finish…

quoll20:09:18

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

quoll20:09:06

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

quoll20:09:49

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

quoll20:09:55

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

quoll20:09:22

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

quoll20:09:46

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

Madara Uchiha20:09:00

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

Madara Uchiha20:09:10

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

Madara Uchiha20:09:29

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?

quoll20:09:45

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

quoll20:09:18

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

quoll20:09:46

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

quoll20:09:58

anyway…. I have to go

quoll20:09:40

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

Madara Uchiha20:09:16

That's fine, it's really helpful

Madara Uchiha20:09:22

Thanks a lot for your time!

quoll20:09:29

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 🙂

quoll20:09:34

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

quoll20:09:03

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

quoll20:09:47

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

Madara Uchiha20:09:05

I think the result is wrong though 😛

Madara Uchiha20:09:23

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

Madara Uchiha20:09:46

That should be something like

Madara Uchiha20:09:28

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