[crntaylor]

"Turning your code inside out" is a great piece of advice, as it often opens up abstractions and refactorings that you didn't realize where there to begin with. The same idea is behind several common object-oriented design patterns (Command, Mediator, Strategy, Visitor) but it's baked into to many functional programming languages.

For example, say we want to write a function to compute square roots. A common approach to computing sqrt(n) is to start with a guess of x = 1.0, and keep replacing x with (0.5 * (x + n/x) until the relative difference between subsequent guesses is small enough.

  sqrt n = loop x0 x1
   where
    loop x y = if converged x y
      then y
      else loop y (0.5 * (y + n/y))
    converged x y = abs (x/y - 1) < 1e-10
    x0 = 1.0;
    x1 = 0.5 * (1.0 + 1.0/n)

That's good, but it has the test for convergence all mixed up with the logic for generating the guesses. What if we could factor out the code that generates an infinite sequence of guesses?

  sqrtGuesses n = go 1.0
   where
    go x = x : go (0.5 * (x + n/x))

Note that this works in Haskell because of laziness, but it's simple in any language that has a mechanism for delaying computations. Now we've decoupled the method for generating a sequence of guesses, we can write a function that checks for relative convergence

   converge (x:y:rest) = if abs (x/y - 1) < 1e-10
     then y
     else converge (y:rest)

and define the square root function in terms of these

   sqrt n = converge (sqrtGuesses n)

The logic of the program is now much cleaner, and we've got a useful function 'converge' which can be re-used in other parts of the program.

This kind of 'turning inside out' is often possible in functional languages, often leads to more compact and more compositional code, and is one of the reasons that I enjoy programming functionally so much.

[dmlorenzetti]

Nice example, but to those considering implementing this in their own code, please don't use that convergence test in practice.

First, you really don't want to do that division x/y, which is slow, and which fails if y==0. It's much cheaper and safer to compare "abs(x-y) < 1e-10*y".

Also, you almost always want to compare (x-y) to an absolute convergence limit (in addition to your relative tolerance), in case x and y are very near zero.

Finally, if you really want a generic converge function that can be re-used elsewhere, you might want to allow for non-convergent processes. This requires tracking the number of iterations, and bailing when it gets too large.

By the way, now that your convergence function wants to know (x-y) rather than x and y individually, you might consider rewriting your logic functions to return the predicted change, rather than the final state. This avoids forcing a re-calculation of the change, which typically was already known in the logic function. It also avoids floating-point problems in which the calculated change x-y differs from the predicted change that produced y in the first place.

[tikhonj]

Of course, part of the beauty of his approach is that you can incorporate most of your changes just by editing the converge function and not messing up the rest of the code.

The last point does require changing the main code, but it's still easier to do with an external converge function like this.

[thaumasiotes]

> First, you really don't want to do that division x/y, which is slow, and which fails if y==0. It's much cheaper and safer to compare "abs(x-y) < 1e-10*y".

I might be missing something, but won't your cheaper and safer fragment also fail when y is zero (or negative)?

[dmlorenzetti]

Sorry, I wasn't clear. I meant that performing the test, as originally given, will induce a divide-by-zero error. The modified test is safe against that; however, as you point out, it will still fail to indicate convergence (which is one reason to include an absolute tolerance as well).

And as you point out, you need to take the abs(y) as well, on the right-hand side.

Thanks for adding clarity.

[JoshTriplett]

The other nice thing about factoring code like this: it often turns up patterns that match existing library functions. For instance, most of sqrtGuesses can be replaced with the "iterate" function:

    sqrtGuesses n = iterate (\x -> (0.5 * (x + n/x))) 1.0

[AlexanderDhoore]

Am I dreaming, or is this an example straight from SICP? (I remember something like this...)

EDIT: Ok, so obviously not "straight" from SICP. But pretty close.

Chapter 1: "Example: Square Roots by Newton's Method" http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html...

[crntaylor]

SICP has something to do with square roots in the first chapter, although I don't think they do this particular refactoring. I first saw it (or something like it) in John Hughes' Why Functional Programming Matters.

Which, by the way, is an excellent paper and totally worth reading.

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pd...

[lisper]

Well, it can't be straight out of SICP because SICP uses Scheme and this code is in Haskell. And, in fact, if you did a straightforward translation of the Haskell code back into Scheme it wouldn't work. Figuring out why it doesn't work in Scheme but it does in Haskell is left as an exercise.

[dmunoz]

Of course, in later chapters SICP covers both streams [0] and lazy evaluation in the interpreter [1]. It's a really great book! I'm completely jealous of anyone who was introduced to CS via a serious studying of SICP.

[0] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.htm...

[1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-27.htm...

[obblekk]

scheme lists aren't lazily generated?

[davexunit]

You use streams a la SRFI-41 for this.

[brudgers]

Or Lazy Racket [in so far as Racket is a Scheme].

http://docs.racket-lang.org/lazy/

[agumonkey]

These is the kind of `combinator` that you can see in "functional javascript" by M.Fogus or " JavaScript Allongé" by R.Braithwaite. IIRC OnLisp also talk about this kind of things (not surprisingly).

[revelation]

C# can do this: http://dotnetfiddle.net/dCm475

(Sorry, it's just a not-so-well-known but awesome feature)

[profquail]

Now here's the same example in F# (a functional language); it compiles into IL similar to that produced by your C# code. Which do you find more readable?

    module Program =
        let n = 42
    
        let rec sqrtGuesses x = seq {
            yield x
            let next_x = 0.5 * (x + (float n / x))
            yield! sqrtGuesses next_x }

        sqrtGuesses 1.0
        |> Seq.pairwise
        |> Seq.pick (fun (x, y) ->
            if abs (x - y) < 1E-10 then Some y else None)
        |> System.Console.WriteLine
        
        System.Console.WriteLine (sqrt (float n))

[daxfohl]

You could use `Seq.scan` to get rid of the manual recursion:

    let n = 42.
        
    Seq.initInfinite float 
    |> Seq.scan (fun x _ -> 0.5 * (x + n/x)) 1.0 
    |> Seq.pairwise
    |> Seq.pick (fun (x, y) -> if abs <| x-y < 1E-10 then Some y else None)
    |> printf "%f"

    printf "%f" <| sqrt n

[darklajid]

Thank you for posting this.

When I saw the original version in F# I thought "I think I can do better" after a long absence from using F#. When I got back to my laptop and searched for the to-be-improved snippet I saw yours.

Now I'm hooked again.

[daxfohl]

Note given appropriate `MyLinqExt.Scan` and `MyLinqExt.Pairwise`, you could write this in C# just as concisely.

[darklajid]

Hmm.. No. :) I guess that's discussed all over the thread here. I do like C# in general and agree that it can be used in a functional style, but 'just as concisely'? Can't agree with that.

Needs the boilerplate (class definition, Main vs. .fsx for example), most keywords/methods seem to be longer (especially the Linq ones, SelectMany, FirstOrDefault etc) and there's no inherent way to build a pipeline as in "no |>".

Obviously you can write quite similar code in C# and I would agree that C# doesn't make it especially hard, is even a roughly decent language for that sort of stuff. Still, the F# snippet looks a lot nicer to me.

Which leads to .. Just a matter of preference, ymmv etc - there's no claim of superiority here.

[username223]

It's a wash. To understand that thing you posted, I'd have to look up what the exclamation point does to "yield", why adding it forces you to repeat the function name, and whether those "|>" sequences are typos or some weird operator. The other version has some random StudlyCaps, I have to look up. Meh.

[codygman]

Well it's only a wash if you are familiar with one and not the other (and that's the case IIUC). You don't intuitively know what the C# version does either.

For future reference "|>" like "$" in haskell is just short hand for a start and end parenthesis and end of expression or next instance of "|>" or "$".

So in Haskell:

    sum $ filter (> 2) [0..10]

is a less noisy way of saying:

    sum(filter (>2) [0..10])

About the exclamation points, I believe it causes it to evaluate and has to do with ensuring the expression is evalauted. At least that is the case in haskell.

[fleitz]

Imperative / shell programmers may be more familiar with |> as a pipe.

  echo "Hello World" | wc -c

  let wc x:String =
    x.length
  "Hello World" |> wc

are equivalent

[platz]

|> would be the flip of $ since the arg comes before the function

[dllthomas]

So equivalent to Control.Lens.(&)

[Chattered]

yield and yield! are both keywords used in sequence expressions. To compute a sequence of type seq<'T>, you can use a sequence expression, in which the yield keyword takes a value of type 'T, and adds that value to the computed sequence, while yield! takes a value of type seq<'T> and appends that value to the computed sequence.

You also have keywords "return" and "return!" for F#'s version of monads. In Haskell, "return" is just a function, while "return!" is not needed (though I wish it was present in Scala).

[profquail]

In F#, yield emits a new element in the sequence (just as in C#), while yield! emits all of the elements from another sequence you provide. This effectively allows you to "splice" sequences together, or create a new sequence by prepending/appending some elements to an existing sequence.

As another commenter mentioned below, yield! has nothing to do with repeating the function name -- the name is repeated because it's a recursive function (i.e., a function which calls itself). So the sqrtGuesses function produces a sequence which emits (yields) the value it's given (x), computes the next value of x, stores it in the variable next_x, then emits all of the values in the sequence produced by calling sqrtGuesses for the next value of x (next_x).

The |> is called the "forward pipeline operator" in F#, and it's very simple -- whereas you normally call a function f with a value x by writing f x, you can swap the order of the arguments with |> to write x |> f. This effectively allows you to write nested function applications without all of the parentheses: f(g(h(x)) can instead be written x |> h |> g |> f or h x |> g |> f or whatever.

[Chattered]

The function name is repeated because it's recursive!

[jasallen]

For those complaining about the verbosity of c#, here is an alternate c# representation:

    public static void Main()
    {
        const int n = 21;

        Observable.Generate<double,double>(1, x=>true, x=> 0.5 * (x + (n/x)), x=>x )
        .Scan(new {prv = 0d, cur = 0d}, (prev, curr) => new {prv = prev.cur, cur = curr})
        .FirstAsync(_ => Math.Abs(_.cur - _.prv) < 1E-10)
        .Select(_ => _.cur)
        .Subscribe(Console.WriteLine);

        // this is just to compare values, so is not part of the solution
        Console.WriteLine(Math.Sqrt(n)); 
        Console.ReadLine();
    }

That's is, everything you need to run the program (technically one line of code, line breaks are for readability). And its non-destructive, has no side effects and is pretty easy to read.

I would never argue that c# is a 'proper' functional language, but the poster above wrote in the style of idiomatic java, something a lot of c# devs do. I don't think c# has an 'idiomatic'. It is very flexible, and while never truly functional, can be also be used like a scala.

[crntaylor]

Having someone re-write my 7 line Haskell program into 40+ lines of C# is the best argument I can think of for why it's worth learning a functional programming language ;)

[gdy]

This kind of lying (why count the usage example?) and gloating attitude is what I find repulsive in Haskell community.

[alipang]

Downvoted. I think the ";)" indicates pretty well that this is tongue in cheek. I wouldn't draw any conclusions about the Haskell community, which is very nice, from this.