Fork me on GitHub
#braveandtrue
<
2018-12-20
>
Felipe Oliveira01: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
Felipe Oliveira19: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 šŸ˜„

Felipe Oliveira19: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.

Felipe Oliveira19: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.

Felipe Oliveira19:12:49

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

Felipe Oliveira19:12:35

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

Felipe Oliveira19: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.

Felipe Oliveira20: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