8 ms·
"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.
by crntaylor 13y ago
"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.
- agumonkey 13y agoThese 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).
- AlexanderDhoore 13y agoAm 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#%_sec_1.1.7 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html...
- lisper 13y agoWell, 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.
- obblekk 13y agoscheme lists aren't lazily generated?
- dmunoz 13y agoOf 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.html#%_sec_3.5 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.html#%_sec_4.2 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-27.htm...
- crntaylor 13y agoSICP 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.pdf http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pd...
- dmlorenzetti 13y agoNice 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 13y agoOf 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 13y ago> 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 13y agoSorry, 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.
- revelation 13y agoC# can do this: http://dotnetfiddle.net/dCm475 http://dotnetfiddle.net/dCm475 (Sorry, it's just a not-so-well-known but awesome feature)
- profquail 13y agoNow 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))
- username223 13y agoIt'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 13y agoWell 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 13y agoImperative / 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
- JoshTriplett 13y agoThe 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