35 people like it.

# Project Euler #2

Solution to Project Euler problem 2: Find sum of even terms in fibonacci sequence which do not exceed four million. Comments about the first version: 1. It does't use memoize becouse of recursive call to unmemoized function "fibs". So it take over 20 sec to get answer. A minor change ("fibs" to "fibs' ") reduces this time to 140ms.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: ``` ``````//generic memoize function from http://blogs.msdn.com/b/dsyme/archive/2007/05/31/a-sample-of-the-memoization-pattern-in-f.aspx let memoize (f: 'a -> 'b) = let t = new System.Collections.Generic.Dictionary<'a,'b>() fun n -> let ok, res = t.TryGetValue(n) if ok then res else let res = f n t.Add(n,res) res let rec fibs n = let fibs' = fun n -> match n with 0 -> 1 | 1 -> 1 | _ -> (fibs (n - 1)) + (fibs (n - 2)) memoize(fibs') n let rec fibSeq n = if fibs n > 4000000 then [] else fibs n :: fibSeq (n + 1) printf "sum: %d\n" (fibSeq 1 |>List.filter (fun x -> x % 2 = 0) |> List.sum) (*alternative version *) let rec fibonacci m n = match n with | x when x>= 4000000 -> 0 | x when x%2=0 -> n + fibonacci n (n+m) | x -> 0 + fibonacci n (n+m) let v = fibonacci 0 1 printfn "%d" v ``````
val memoize : f:('a -> 'b) -> ('a -> 'b) (requires equality)

Full name: Script.memoize
val f : ('a -> 'b) (requires equality)
val t : System.Collections.Generic.Dictionary<'a,'b> (requires equality)
namespace System
namespace System.Collections
namespace System.Collections.Generic
Multiple items
type Dictionary<'TKey,'TValue> =
new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
member Add : key:'TKey * value:'TValue -> unit
member Clear : unit -> unit
member Comparer : IEqualityComparer<'TKey>
member ContainsKey : key:'TKey -> bool
member ContainsValue : value:'TValue -> bool
member Count : int
member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
member Item : 'TKey -> 'TValue with get, set
...
nested type Enumerator
nested type KeyCollection
nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
System.Collections.Generic.Dictionary() : unit
System.Collections.Generic.Dictionary(capacity: int) : unit
System.Collections.Generic.Dictionary(comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit
System.Collections.Generic.Dictionary(dictionary: System.Collections.Generic.IDictionary<'TKey,'TValue>) : unit
System.Collections.Generic.Dictionary(capacity: int, comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit
System.Collections.Generic.Dictionary(dictionary: System.Collections.Generic.IDictionary<'TKey,'TValue>, comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit
val n : 'a (requires equality)
val ok : bool
val res : 'b
System.Collections.Generic.Dictionary.TryGetValue(key: 'a, value: byref<'b>) : bool
System.Collections.Generic.Dictionary.Add(key: 'a, value: 'b) : unit
val fibs : n:int -> int

Full name: Script.fibs
val n : int
val fibs' : (int -> int)
val fibSeq : n:int -> int list

Full name: Script.fibSeq
val printf : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printf
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val x : int
val sum : list:'T list -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sum
val fibonacci : m:int -> n:int -> int

Full name: Script.fibonacci
val m : int
val v : int

Full name: Script.v
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn