Project Euler #2

 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 Head : '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