Sometimes I still get stuck trying to translate procedural code into functional code.
Is there a list of functional idioms/snippets that are mapped to procedural idioms/snippets?
Edit
Since there doesn't seem to be a centralized website of these snippets, I am turning this into a community wiki. Please paste any procedural -> functional snippets here.
Oh, now this is a nifty question. Here are some, code snips in python or something cloe:
for loops can be replaced with iterators
stripped_list = [line.strip() for line in line_list]
for loops can be replaced with apply or map or filter
map(upper, ['sentence', 'fragment']) ['SENTENCE', 'FRAGMENT']
nested for loops with composition of functions
tail recursion in place of loops
generator expressions in place of for loops
sum(x*x for x in range(10))
Old homework question:
The function
(define f-imperative (y) (x) ; x is a local variable
(begin
(set x e)
(while (p x y)
(set x (g x y)))
(h x y)))
is in a typical imperative style, with assignment and looping. Write an equivalent function f-functional that doesn't use the imperative features begin (sequencing), while (goto), and set (assignment). You may use as many ``helper functions'' as you like, as long as they are defined using let or letrec and not at top level.
One solution:
; The idea is simple:
; Use parameter passing for binding the values
; of the variables and recursion instead of iteration.
;
; For those who like theory this is the main argument for proving
; that recursive functions (LISP, lambda calculus) have the same
; computational power as any imperative programming language.
(define f-functional (y)
(letrec (
(f-helper (lambda (x y)
(if (p x y)
(f-helper (g x y) y)
(h x y)))))
(f-helper e y)))
; Notice that y in f-helper is invariant. Therefore, we can rewrite
; f-helper without y as follows.
(define f-functional (y)
(letrec (
(f-helper (lambda (x)
(if (p x y)
(f-helper (g x y))
(h x y)))))
(f-helper e)))
; This is not the only solution, though I think it is one of the
; nicer ones.
(Edited from this post on fshub)
The first time I went to reach for break/continue in OCaml/F#, it threw me for an (infinite) loop, so to speak, because no such thing exists! In OCaml, one can use exceptions to break from a loop because they are very cheap, but in F# (in .NET) the overhead is quite high and not useful for "normal" flow control.
This came up when playing with sort algorithms a while back (to kill some time), which make heavy use of repeat/until and break. It hit me that recursive tail call functions can achieve exactly the same result, with only a slight ding to readability. So, I threw out 'mutable bDone' and 'while not bDone' and tried writing the code without these imperative constructs. The following distills out just the looping parts and shows how to write repeat/until, do/while, while/do, break/continue, and test-in-the-middle style code using tailcalls. These all appear to run at exactly the same speed as a traditional F# 'while' statement, but your mileage may vary (some platforms may not properly implement tailcall and therefore may stack fault until they are patched). At the end is a (bad) sort algorithm written in both styles, for comparison.
Let's start with a 'do/while' loop, written in traditional F# imperative style, then look at functional variations which provide both the same type of loop, as well as different semantics like while/do, repeat/until, test in the middle, and even break/continue (without monads.. um, workflows!).
#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000
let imperDoWhile() =
let mutable x = 0
let mutable bDone = false
while not bDone do
f()
x <- x + 1
if x >= N then bDone <- true
Ok, that's easy enough. Keep in mind that f() is always called at least once (do/while).
Here is the same code, but in a functional style. Note that we don't need to declare a mutable here.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
We can spin that to a traditional do/while by putting the function call inside the if block.
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
How about repeating a block until some condition is true (repeat/until)? Easy enough...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
What was that about a monad-less break? Well, just introduce a conditional expression which returns 'unit', as in:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
How about continue? Well, that's just another call to loop! First, with a syntax crutch:
let funBreakContinue() =
let break' () = ()
let rec continue' () =
let x = g()
if x > N then break'()
elif x % 2 = 0 then
f(); f(); f();
continue'()
else
f()
continue'()
continue'()
And then again without the (ugly) syntax crutch:
let funBreakContinue'() =
let rec loop () =
let x = g()
if x > N then ()
elif x % 2 = 0 then
f(); f(); f();
loop()
else
f()
loop ()
loop()
Easy as pie!
One nice result of these loop forms is that it makes it easier to spot and implement states in your loops. For example, a bubble sort continually loops over an entire array, swapping values that are out of place as it finds them. It keeps track of whether a pass over the array produced any exchanges. If not, then every value must be in the right place, so the sort can terminate. As an optimization, on every pass thru the array, the last value in the array ends up sorted into the correct place. So, the loop can be shortened by one each time through. Most algorithms check for a swap and update a "bModified" flag every time there is one. However, once the first swap is done, there is no need for that assignment; it's already set to true!
Here is F# code which implements a bubble sort (yes, bubble sort is terrible algorithm; quicksort rocks). At the end is an imperative implementation which does not change state; it updates the bModified flag for every exchange. Interestingly, the imperative solution is faster on tiny arrays and just a percent or two slower on large ones. (Made for a good example, though).
let inline sort2 f i j (a:'a array) =
let i' = a.[ i ]
let j' = a.[ j ]
if f i' j' > 0 then
a.[ i ] <- j'
a.[ j ] <- i'
let bubble f (xs:'a array) =
if xs.Length = 0
then ()
let rec modified i endix =
if i = endix then
unmodified 0 (endix-1)
else
let j = i+1
sort2 f i j xs
modified j endix
and unmodified i endix =
if i = endix then
()
else
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
modified j endix
else
unmodified j endix
in unmodified 0 (xs.Length-1)
let bubble_imperitive f (xs:'a array) =
let mutable bModified = true
let mutable endix = xs.Length - 1
while bModified do
bModified <- false
endix <- endix - 1
for i in 0..endix do
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
bModified <- true
done
done
The fold is a very interesting function, that is central in many functional algorithms. Let's say we want to add all the elements of a list. In procedural code, you would generally create an accumulator variable and set it to 0, then iterate through the list and increment the accumulator by the item.
In Ocaml, you perform the same action in a functional way by using fold:
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
Using fold, you can for example count the number of words in the list and concatenate them at the same time:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
Another useful utilisation of fold is to copy a vector into a set. As sets in Ocaml are immutable, you effectively need to create for each item of the list a new set that contains the previous set plus that new item.
module Int = struct type t = int let compare = compare end;;
module IntSet = Set.Make(Int);;
let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];;
val s : IntSet.t = <abstr>
IntSet.elements s;;
- : IntSet.elt list = [1; 2; 3]
Here, our initial object is an empty set, and at each call, a new set is created, based on the previous set and the current item by using IntSet.add.
Implement fold recursively yourself once, to know how it is done under the hood, then use the built-in version everywhere. Even in C++, with std::accumulate!
The PLEAC project has almost exactly this as its goal - implement all the examples in the perl cookbook in other languages. Here'a the links to the ocaml version (which is one of three 100% complete) http://pleac.sourceforge.net/pleac_ocaml/index.html