logo
down
shadow

Simple explanation of List.Fold and List.Foldback in F#


Simple explanation of List.Fold and List.Foldback in F#

Content Index :

Simple explanation of List.Fold and List.Foldback in F#
Tag : fhash , By : Novi Indrayani
Date : November 25 2020, 07:22 PM

I hope this helps you . The best way to understand it is with an example. Imagine you have list of numbers and you want to find out the total. In imperative programming you could do this:
let numbers = [ 19 ; 52 ; 35 ; 27]

let mutable total = 0
for n in numbers do
    total <- total + n

printfn "%A" total   // 133
numbers
|> List.fold (fun total n -> total + n) 0
|> printfn "%A"    // 133
val List.fold: 
   folder: 'State -> 'T -> 'State ->
   state : 'State  ->
   list  : 'T list 
        -> 'State
let rec totalF total ns =
    match ns with
    | []        ->         total
    | n :: tail -> totalF (total + n) tail

numbers
|> totalF 0
|> printfn "%A"    // 133
let rec totalF f total ns =
    match ns with
    | []        -> total
    | n :: tail -> totalF f (f total n) tail

numbers
|> totalF (fun total n -> total + n) 0
|> printfn "%A"    // 133
val totalF: 
   f    : 'a -> 'b -> 'a ->
   total: 'a             ->
   ns   : 'b list        
       -> 'a

Comments
No Comments Right Now !

Boards Message :
You Must Login Or Sign Up to Add Your Comments .

Share : facebook icon twitter icon

Asymptotic time complexity of List.fold and foldBack


Tag : algorithm , By : Ansari
Date : March 29 2020, 07:55 AM
I wish did fix the issue. If each inner operation is Θ(1), List.fold and List.foldBack is O(n) where n is the length of the list.
However, to estimate asymptotic time complexity, you need to rely on Θ(1) operations. In your example, things are a little more subtle.
  m + ... + m // n occurences of m
= O(m*n)
  0 + m + 2*m + ... + (n-1)*m // each time length of left operand increases by m
= m*n*(n-1)/2
= O(m*n^2)

Why is List.foldBack as fast as List.fold


Tag : performance , By : ffmmjj
Date : March 29 2020, 07:55 AM
I wish this helpful for you If you look at the source for List.foldBack you can see that it converts the list into an array and then iterates over it from the end applying the accumulator function to get the result.

Example of the difference between List.fold and List.foldBack


Tag : fhash , By : Anonymous
Date : March 29 2020, 07:55 AM
To fix this issue You don't see a difference in your example because you chose a function such that for any x1 and x2:
(acc - x1) - x2 = (acc - x2) - x1
x1 :: (x2 :: acc) <> x2 :: (x1 :: acc)
List.fold (fun acc x -> x :: acc) [] [1; 2; 3; 4; 5]
// val it : int list = [5; 4; 3; 2; 1]

List.foldBack (fun x acc -> x :: acc) [1; 2; 3; 4; 5] [];;
// val it : int list = [1; 2; 3; 4; 5]

F# - splitting list of integers into odds and evens using List.foldBack


Tag : list , By : Patastroph
Date : March 29 2020, 07:55 AM
I hope this helps . Your code doesn't actually check whether the value is odd or even – it just adds it to the 'odds' list regardless, and swaps the 'odds' and 'evens' lists for each value. Fixing both is straightforward, if ugly:
let oddEvenSplit listToSplit =
    List.foldBack
        (fun x (even, odd) -> if x % 2 = 0 then (x::even, odd) else (even, x::odd))
        listToSplit
        ([], [])
let oddEvenSplit listToSplit =
    let impl x (even, odd) = if x % 2 = 0 then (x::even, odd) else (even, x::odd)
    List.foldBack impl listToSplit ([], [])

// or

let oddEvenSplit listToSplit =
    (listToSplit, ([], [])) ||> List.foldBack (fun x (even, odd) ->
        if x % 2 = 0 then (x::even, odd) else (even, x::odd))

Why is the signature of foldBack so much different from fold in F#?


Tag : fhash , By : jaset
Date : March 29 2020, 07:55 AM
shadow
Privacy Policy - Terms - Contact Us © scrbit.com