20 people like it.

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.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 

let pascal n =
    //inner function that use tail-call recursion
    let rec _pascal accu x top =
        match x with
        | x when x = top -> accu
        | x -> let nv = let h = List.head accu 
                        //Lets code the 'visual' method using map2
                        List.map2 (+) (h @ [0]) (0 :: h) 
               _pascal (nv :: accu)  (x + 1) top
    _pascal [[1]] 1 n
val pascal : n:int -> int list list

Full name: Script.pascal
val n : int
val _pascal : (int list list -> int -> int -> int list list)
val accu : int list list
val x : int
val top : int
val nv : int list
val h : int list
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 head : list:'T list -> 'T

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

Full name: Microsoft.FSharp.Collections.List.map2
Raw view Test code New version

More information

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

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.