Fork me on GitHub
#braveandtrue
<
2018-12-20
>
felipebarros01:12:50

Sorry for answering a day later, but our time zones are probably way off and I had a busy day. 🙂

manutter5111:12:51

No problem, Slack is actually not too bad at compensating for timezone offsets, if you don’t mind waiting a bit for replies. 🙂

manutter5111:12:11

I played with writing a my-comp function, and I used recursion (not reduce). I will say that I’ve been writing Clojure for 7 or 8 years, and I’m pretty comfortable in it, but I still found this problem a bit tricky, even having a pretty good idea how it should be solved.

manutter5111:12:02

The basic pattern of recursion is that you figure out the easy problem, also known as the “base case”, and then figure out how to have the function solve slightly more complex problems by calling itself. And it’s only slightly more complex. You don’t have to figure out all possible answers, you just have to figure out two cases: the base case, and the “base case + 1".

manutter5112:12:52

So, for example, to write a factorial function, you first solve the simple case where n = 1

(defn fact [n]
  (if (= n 1) 
    1
    ,,,
  ))

manutter5112:12:13

Then for numbers greater than 1, you take the definition of “factorial” and try to find some way to phrase it in terms of itself.

factorial(n) = n * (n - 1) * (n - 2) * ... 2 * 1
is the “naive” definition of factorial, but we can write that more concisely by defining it recursively: factorial(n) = n * factorial(n - 1) So in Clojure terms we get this:
(defn fact [n]
  (if (= n 1) 
    1
    (* n (fact (dec n)))))

manutter5112:12:48

So far so good? This is the “easy” part — we’re doing recursion with data, and getting back a result that is data. What makes Chapter 5 tricky is that we want to do the same thing with HOFs (Higher Order Functions).

manutter5112:12:52

We still want to solve the problem the same way: look for a simple, base case that we know the answer to, and then try to find a way to define our fn recursively so that it eventually winds down to our simple base case.

manutter5112:12:48

For this particular problem, Brave and True gives us the simple base case: “comp” with two functions.

(defn brave-comp [f g]
  (fn [& args]
    (f (apply g args))))
Now all we have to do is figure out the recursive case.

manutter5112:12:39

I’ll stop there so you can have a look at this and ask any questions. This might be enough to get you heading in the right direction, but recursion is a tricky concept to master, and doubly tricky when you’re trying to apply recursion to higher-order functions. We’re pretty close to solving this though, so you might want to take a whack at this on your own and see if you can crack it.

👏 4
felipebarros19:12:53

Awesome explanation! Thank you 🙂 I have tried many hours yesterday after I spoke here, and have a file full of unfinished half-thoughts, but with this explanation I think that I have at least a clue. Well, it's not working right now, but I believe I'm not that far, so I'll keep trying a bit more 😄

felipebarros19:12:02

I really don't get the part of "a way of using recursion that will naturally give you the last-to-first order without reverse" 😕

manutter5119:12:08

Well, I'd say just ignore that part for now and just see if you can figure out the recursive bit.

manutter5119:12:46

If you get the recursive bit, the last-to-first order bit will kind of solve itself.

felipebarros19:12:03

This is what I have so far

(defn my-comp [f & fs]
  (fn [& args]
    (let [res (apply f args)]
      (loop [[head & tail] fs
             result res]
        (if (not (nil? tail))
          (recur tail (apply head (vector result))))))))
But it isn't working 😕 gives me "nil" always.

felipebarros19:12:49

I have no experience with forcing evaluation with apply, so maybe this is where it's going wrong.

felipebarros19:12:35

And using reverse I could probably just ask for [& fs] in my-comp and reverse it, extract the head, etc.

felipebarros19:12:09

But without it, I have no idea.

manutter5120:12:31

My solution does not use loop/recur at all.

manutter5120:12:00

It does have the base case, though.

manutter5120:12:11

The structure of my solution looks very similar to the factorial function I used as an example.

felipebarros20:12:05

I see, let me try a bit more then 🙂

manutter5120:12:34

Good luck. 🙂

jaide21:12:09

Though you can use recur without a loop. It makes recursion a bit safer in clojure but you’re probably not recursing a lot with a comp function though 😄

manutter5121:12:23

You only need to recurse once, and you don’t need recur to do it. 😉

jaide21:12:58

We’re talking about a comp implementation that takes 1 or more functions right?

manutter5121:12:54

2 or more functions (you could do it so that it supports 1 function, but that’s kind of an edge case and it nicer not to worry about that until you get the 2-or-more version working)

manutter5121:12:54

If you look at my factorial function above, the function definition contains 1 call back to itself, without loop or recur.

jaide21:12:47

Oh right, I think I used the wrong term. It still iterates n times. Just as your comp will have to call itself for however many functions are provided to it?

manutter5121:12:49

Right, it will keep recursing until it gets down to the base case, which is the 2-argument version of my-comp

jaide21:12:47

Ah ok, we’re on the same page then. Isn’t it preferred to use recur though rather than directly calling the function?

manutter5121:12:08

Depends on your goal: if you want to avoid blowing the stack for long sequences, recur is better. If you want to illustrate the principle of recursion, it’s nice not to have to worry about it, and just call directly--it makes the code a little simpler.

manutter5121:12:21

Arguably, comp is a special case: you’ll only be using it for code that you write, and you’re unlikely to try and comp together so many functions that you blow the stack. (It could happen, though, in which case you’ll need the recur version.)

manutter5121:12:46

In general real-world programming, it’s usually better to use recur to avoid the stack overflow problem.

manutter5121:12:17

Hmm, “Depends on your goal..” etc sounds snooty. I should have just said, “Yes, usually you would prefer recur and I’m just making an exception in this case to make the exercise simpler.”

jaide21:12:28

You’re right. The code is simpler doing it directly the solution I had in mind would only have recur’d the inner anonymous function when we need to reach the outer my-comp function.

jaide21:12:20

You could probably make that work by adding more args to the anonymous function but likely not practical or worth it

jaide21:12:27

Thanks for explaining.

manutter5121:12:35

my pleasure 🙂

👍 4