Pascal's Triangle

Returns the pascal triangle in a 2D list . This snippet computes rows translating the 'visual' method taught at school into Lists and the usage of map2 function. It takes almost 5 seconds to compute 5000 rows.

Copy Source
Copy Link
Tools:
 1: let pascal n =
 2:     //inner function that use tail-call recursion
 3:     let rec _pascal accu x top =
 4:         match x with
 5:         | x when x = top -> accu
 6:         | x -> let nv = let h = List.head accu 
 7:                         //Lets code the 'visual' method using map2
 8:                         List.map2 (+) (h @ [0]) (0 :: h) 
 9:                _pascal (nv :: accu)  (x + 1) top
10:     _pascal [[1]] 1 n
val pascal : int -> int list list

Full name: Snippet.pascal
val n : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val _pascal : (int list list -> int -> int -> int list list)
val accu : int list list

  type: int list list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<int list>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<int list>
  implements: System.Collections.IEnumerable
val x : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val top : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val nv : int list

  type: int list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<int>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<int>
  implements: System.Collections.IEnumerable
val h : int list

  type: int list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<int>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<int>
  implements: System.Collections.IEnumerable
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.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
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'T>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'T>
  implements: System.Collections.IEnumerable
val head : 'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.head
val map2 : ('T1 -> 'T2 -> 'U) -> 'T1 list -> 'T2 list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map2

More information

Link: http://fssnip.net/2Y
Posted: 3 years ago
Author: Horacio Nuñez (website)
Tags: math, pascal, algorithms, lists