Mindset shifts for functional programming (with Clojure)

Post by chriswarbo » Wed, Apr 05, 2023, 3:17 PM UTC

twic wrote: post #50

chriswarbo wrote: post #28

Earlier quoted context omitted.

> Nobody has yet convinced me that recursion has any sustained advantage over looping. Looping may require trampolining or defunctionalisation, whilst recursion can be written much more directly and simply. As a very simple example (in pseudocode): even(n: uint): boolean = n match { case 0: true case n: odd(n-1) } odd(n: uint): boolean = n match { case 0: false case n: even(n-1) } Whilst these are pretty silly implem…

I'm not going to argue this is good, but it's fairly analogous: boolean isEven(int n) { boolean even = true; for (; n > 0; --n) even = !even; return even; }

Post by Herval_freire » Wed, Apr 05, 2023, 3:27 PM UTC

KRAKRISMOTT wrote: post #53

Herval_freire wrote: post #46

Earlier quoted context omitted.

>Nobody has yet convinced me that recursion has any sustained advantage over looping. Recursion gives you a stack by default. You don't have to explicitly think about the stack. In looping the stack must be explicit. Recursion and looping are the same thing. Recursion can be mechanically translated to a for loop and a stack, the concepts are isomorphic.

On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. Non optimized recursion is not hard to understand, the problem is any performant recursive code needs to be manually rewritten as tail recursive which adds a lot of complexity. Bu…

Post by janetacarr » Wed, Apr 05, 2023, 3:33 PM UTC

sharas- wrote: post #54

janetacarr wrote: post #37

Earlier quoted context omitted.

Clojure data type's are fantastic, but the main thesis of my post isn't what's required for FP in Clojure, rather, what's required to become comfortable with pure functional programming concepts which is why I reference Haskell a lot in the post. The examples just happen to be in Clojure. Sorry for the confusion.

I get it. But my point is that clojure is not snobbish about pure functional programming. It's angle is data centricity. Very different to haskell in that respect and type centricity of it.

Post by chriswarbo » Wed, Apr 05, 2023, 3:45 PM UTC

chriswarbo wrote: post #28

roenxi wrote: post #15

> Recursion over Looping Part of what makes Clojure a great programming language is that you don't have to believe this if you don't want to. Nobody has yet convinced me that recursion has any sustained advantage over looping. Using a loop is generally bad practice if a more specialised operation is available (don't loop if something is a simple map or reduce for example). But if the situation justifies a recursion t…

> Nobody has yet convinced me that recursion has any sustained advantage over looping. Looping may require trampolining or defunctionalisation, whilst recursion can be written much more directly and simply. As a very simple example (in pseudocode): even(n: uint): boolean = n match { case 0: true case n: odd(n-1) } odd(n: uint): boolean = n match { case 0: false case n: even(n-1) } Whilst these are pretty silly implem…

  type STEP[T] = either[T, unit => STEP[T]]

  stepper[T](current: STEP[T]): T = {
    for (result = current; result.isRight(); result = result.value(unit))
    return result
  }

  even(n: uint): boolean = stepper(n match {
    case 0: left(true)
    case n: right(() => odd(n-1))
  })

  odd(n: uint): boolean = stepper(n match {
    case 0: left(false)
    case n: right(() => even(n-1))
  })

  type STEP = ODD(n: uint) | EVEN(n: uint) | RETURN(x: boolean)

  even_impl(n: uint): STEP = n match {
    case 0: RETURN(true)
    case n: ODD(n-1)
  }

  odd_impl(n: uint): STEP = n match {
    case 0: RETURN(false)
    case n: EVEN(n-1)
  }

  interpret(current: STEP): boolean = {
    while (!current.isReturn) {
      current = current match {
        case ODD(n): odd_impl(n)
        case EVEN(n): even_impl(n)
      }
    }
    return current.x
  }

  odd(n: uint): boolean = interpret(ODD(n))

  even(n: uint): boolean = interpret(EVEN(n))

Post by twawaaay » Wed, Apr 05, 2023, 5:16 PM UTC

janetacarr wrote: post #36

twawaaay wrote: post #2

> Transformations over Instructions Hell yeah! The problem with "functional" programming is that a lot of people simply don't get you want to push as much of your program to be generic tools that transform things (ie FUNCTIONS!) When I start on a new problem I typically look at what kind of tools (functions) would make the solution concise and readable. Then create the tools and then write the solution with the tools…

I agree with your sentiment about recursion. It took me a damn long time to get used to it. But that's why I call it a mindset shift ;). If the codebase was written in Haskell, then there'd be no looping. Clojure is a bit odd in this case as it has a form called "loop" but it's really just a let binding over a fn, providing a point for `recur` to, well, recur to.