17 people like it.
Like the snippet!
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: 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
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
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
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
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
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
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
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
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
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
Full name: Microsoft.FSharp.Collections.List.map2
More information
| Link: | http://fssnip.net/2Y |
| Posted: | 2 years ago |
| Author: | Horacio Nuñez (website) |
| Tags: | math, pascal, algorithms, lists |