3 people like it.

List2D module

Contains operations for working with 2-dimensional lists.

  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: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 
184: 
185: 
186: 
187: 
188: 
189: 
190: 
191: 
192: 
193: 
194: 
195: 
196: 
197: 
198: 

module List2D =
    type 't list2d =
      | A of 't list2d * 't list2d //above structure
      | B of 't list2d * 't list2d //beside structure
      | E of 't                    //container
      | Empty                      //empty list
    with 
        /// <summary>
        /// list2d transpose: swap A and B
        /// </summary>
        member this.transpose = let rec loop = function 
                                  | A(x, Empty) | A(Empty,x) 
                                  | B(x, Empty) | B(Empty,x) -> loop x
                                  | A(a,b) -> B(loop a,loop b)
                                  | B(a,b) -> A(loop a,loop b)
                                  | a -> a
                                loop this
        /// <summary>
        /// list2d height: number of A
        /// </summary>
        member this.height = let rec loop = function
                                | E(_)  -> 1
                                | Empty -> 0
                                | A(x,y) -> (loop x) + (loop y)
                                | B(x,_) -> (loop x)
                             loop this
        /// <summary>
        /// list2d width: number of B
        /// </summary>
        member this.width = let rec loop = function
                                | E(_)  -> 1
                                | Empty -> 0
                                | A(x,_) -> (loop x) 
                                | B(x,y) -> (loop x) + (loop y)
                            loop this
        /// <summary>
        /// list2d area
        /// </summary>
        member this.area = this.height * this.width

    /// <summary>
    /// list2d map: apply transformation to each element of list2d
    /// </summary>
    /// <param name="f">transformation</param>
    let rec map f = function
                    //| A(x,Empty) | A(Empty,x)              //strip Empty element if you don't really need it
                    //| B(x,Empty) | B(Empty,x) -> map f x
                    | E x -> E(f x)
                    | A(x,y) -> A(map f x, map f y)
                    | B(x,y) -> B(map f x, map f y)
                    | Empty -> Empty
    /// <summary>
    /// list2d reduce: replace "above" and "beside" operators
    /// </summary>
    /// <param name="Af">replacement for above</param>
    /// <param name="Bf">replacement for beside</param>
    let rec reduce Af Bf  =   function
                                  | E(x) -> x
                                  | A(x,Empty) | A(Empty, x) 
                                  | B(x,Empty) | B(Empty, x) -> reduce Af Bf x
                                  | A(x,y) -> Af (reduce Af Bf x) (reduce Af Bf y)
                                  | B(x,y) -> Bf (reduce Af Bf x) (reduce Af Bf y)
                                  | Empty -> failwith "Empty list2d"

    /// <summary>
    /// list2d sum: matrix total
    /// </summary>
    let sum = reduce (+) (+)  
    /// <summary>
    /// Left operator
    /// </summary>
    /// <param name="a">returned parameter</param>
    /// <param name="_b">omitted parameter</param>
    let inline (<<|) (a:'t) (_b:'t) = a 
    /// <summary>
    /// Right operator
    /// </summary>
    /// <param name="_a">omitted parameter</param>
    /// <param name="b">returned parameter</param>
    let inline (|>>) (_a:'t) (b:'t) = b
    /// <summary>
    /// Most top left element of list2d
    /// </summary>
    /// <param name="M">list2d</param>
    let topleft M = reduce (<<|) (<<|) M
    /// <summary>
    /// Most top right element of list2d
    /// </summary>
    /// <param name="M">list2d</param>
    let topright M = reduce (<<|) (|>>) M 
    /// <summary>
    /// Most bottom left element of list2d
    /// </summary>
    /// <param name="M">list2d</param>
    let bottomleft M = reduce (|>>) (<<|) M
    /// <summary>
    /// Most bottom right element of list2d
    /// </summary>
    /// <param name="M">list2d</param>
    let bottomright M = reduce (|>>) (|>>) M
    /// <summary>
    /// Place one element above another element
    /// </summary>
    /// <param name="x">element</param>
    /// <param name="y">element</param>
    let above x y = A(x, y)
    /// <summary>
    /// Place one element beside another element
    /// </summary>
    /// <param name="x">element</param>
    /// <param name="y">element</param>
    let beside x y = B(x, y) 
    /// <summary>
    /// Place element
    /// </summary>
    /// <param name="x">element</param>
    let place x = E x
    /// <summary>
    /// Extract value
    /// </summary>
    let the = function | E x -> x | _ -> failwith "Not a singleton list2d"
    let rec topreduce f = function
                           | E x -> E x
                           | Empty -> Empty 
                           | A(x,E y)
                           | A(E y, x) -> let b = the (topreduce f x) in
                                          E(f b y)
                           | A(x,Empty) | A(Empty,x) -> topreduce f x
                           | B(x,Empty) | B(Empty,x) -> topreduce f x
                           | B(x, y) -> B(topreduce f x,topreduce f y)
                           | a -> failwith (sprintf "%A" a)

    /// <summary>
    /// list2d zip with f: makes pairwise zipping of two list2d
    /// </summary>
    /// <param name="f">zip operator</param>
    /// <param name="M1">first list2d</param>
    /// <param name="M2">second list2d</param>
    let zip f (M1:'t list2d) (M2:'t list2d) = let rec loop a b =
                                                  match a,b with
                                                     | Empty,Empty   -> Empty
                                                     | E(x),E(y)     -> E(f x y)
                                                     | A(x,y),A(u,v) -> A(loop x u,loop y v)
                                                     | B(x,y),B(u,v) -> B(loop x u,loop y v)
                                                     | _             -> failwith "Dimensions mismatch"
                                              loop M1 M2

    /// <summary>
    /// list2d rows. Return list2d of rows
    /// </summary>
    /// <param name="M">list2d</param>
    let rows M = M |> (map (place >> place) >> reduce above (zip beside))
    /// <summary>
    /// list2d columns. Return list2d of columns
    /// </summary>
    /// <param name="M">list2d</param>
    let columns M = M |> (map (place >> place) >> reduce (zip above) beside)
    let rec stripAB M = match M with
                          | A(E x, E y) | B(E x, E y) -> [x; y]
                          | A(E x, y)   | B(E x, y) -> x::(stripAB y)
                          | _ -> failwith "Incorrect constructor"
    /// <summary>
    /// List of list2d rows
    /// </summary>
    /// <param name="M">list2d</param>
    let listrows M = M |> (map (List.singleton >> place) >> reduce above (zip (@))  >> stripAB)
    /// <summary>
    /// List of list2d columns
    /// </summary>
    /// <param name="M">list2d</param>
    let listcols M = M |> map (List.singleton >> place) |> reduce (zip (@)) beside|> stripAB

//Examples
let a = Array2D.zeroCreate<int> 5 5
let mutable k = 0
for i in 0..4 do
      for j in 0..4 do
        a.[i, j] <- k
        k <- k + 1

let toRow (a:'t array) =  
         a.[0..] 
            |> Array.rev 
            |> Array.fold (fun acc el -> List2D.B(List2D.E(el),acc)) List2D.Empty

let toMatrix (a:'t [,]) = 
        let s = seq{for i in [(Array2D.length2 a)-1..-1..0] do
                         yield a.[i,*] |> toRow }
        s |> Seq.fold (fun acc r -> List2D.A(r, acc)) List2D.Empty

let b =
    a 
    |> toMatrix
    |> List2D.map (fun e -> e*2)

b |> List2D.listrows
b.width
b |> List2D.sum
union case list2d.A: 't list2d * 't list2d -> 't list2d
type 't list2d =
  | A of 't list2d * 't list2d
  | B of 't list2d * 't list2d
  | E of 't
  | Empty
    member area : int
    member height : int
    member transpose : 't list2d
    member width : int
union case list2d.B: 't list2d * 't list2d -> 't list2d
union case list2d.E: 't -> 't list2d
union case list2d.Empty: 't list2d
val this : 't list2d
val loop : ('a list2d -> 'a list2d)
val x : 'a list2d
val a : 'a list2d
val b : 'a list2d
val loop : ('a list2d -> int)
val y : 'a list2d
property list2d.height: int with get


 <summary>
 list2d height: number of A
 </summary>
property list2d.width: int with get


 <summary>
 list2d width: number of B
 </summary>
val map : f:('a -> 'b) -> _arg1:'a list2d -> 'b list2d


 <summary>
 list2d map: apply transformation to each element of list2d
 </summary>
 <param name="f">transformation</param>
val f : ('a -> 'b)
val x : 'a
val reduce : Af:('a -> 'a -> 'a) -> Bf:('a -> 'a -> 'a) -> ('a list2d -> 'a)


 <summary>
 list2d reduce: replace "above" and "beside" operators
 </summary>
 <param name="Af">replacement for above</param>
 <param name="Bf">replacement for beside</param>
val Af : ('a -> 'a -> 'a)
val Bf : ('a -> 'a -> 'a)
val failwith : message:string -> 'T
val sum : (int list2d -> int)


 <summary>
 list2d sum: matrix total
 </summary>
val a : 't
val _b : 't
val _a : 't
val b : 't
val topleft : M:'a list2d -> 'a


 <summary>
 Most top left element of list2d
 </summary>
 <param name="M">list2d</param>
val M : 'a list2d
val topright : M:'a list2d -> 'a


 <summary>
 Most top right element of list2d
 </summary>
 <param name="M">list2d</param>
val bottomleft : M:'a list2d -> 'a


 <summary>
 Most bottom left element of list2d
 </summary>
 <param name="M">list2d</param>
val bottomright : M:'a list2d -> 'a


 <summary>
 Most bottom right element of list2d
 </summary>
 <param name="M">list2d</param>
val above : x:'a list2d -> y:'a list2d -> 'a list2d


 <summary>
 Place one element above another element
 </summary>
 <param name="x">element</param>
 <param name="y">element</param>
val beside : x:'a list2d -> y:'a list2d -> 'a list2d


 <summary>
 Place one element beside another element
 </summary>
 <param name="x">element</param>
 <param name="y">element</param>
val place : x:'a -> 'a list2d


 <summary>
 Place element
 </summary>
 <param name="x">element</param>
val the : _arg1:'a list2d -> 'a


 <summary>
 Extract value
 </summary>
val topreduce : f:('a -> 'a -> 'a) -> _arg1:'a list2d -> 'a list2d
val f : ('a -> 'a -> 'a)
val y : 'a
val b : 'a
val sprintf : format:Printf.StringFormat<'T> -> 'T
val zip : f:('t -> 't -> 'a) -> M1:'t list2d -> M2:'t list2d -> 'a list2d


 <summary>
 list2d zip with f: makes pairwise zipping of two list2d
 </summary>
 <param name="f">zip operator</param>
 <param name="M1">first list2d</param>
 <param name="M2">second list2d</param>
val f : ('t -> 't -> 'a)
val M1 : 't list2d
val M2 : 't list2d
val loop : ('t list2d -> 't list2d -> 'a list2d)
val a : 't list2d
val b : 't list2d
val x : 't
val y : 't
val x : 't list2d
val y : 't list2d
val u : 't list2d
val v : 't list2d
val rows : M:'a list2d -> 'a list2d list2d


 <summary>
 list2d rows. Return list2d of rows
 </summary>
 <param name="M">list2d</param>
val columns : M:'a list2d -> 'a list2d list2d


 <summary>
 list2d columns. Return list2d of columns
 </summary>
 <param name="M">list2d</param>
val stripAB : M:'a list2d -> 'a list
val listrows : M:'a list2d -> 'a list list


 <summary>
 List of list2d rows
 </summary>
 <param name="M">list2d</param>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
    interface IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetReverseIndex : rank:int * offset:int -> int
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    ...
val singleton : value:'T -> 'T list
val listcols : M:'a list2d -> 'a list list


 <summary>
 List of list2d columns
 </summary>
 <param name="M">list2d</param>
val a : int [,]
module Array2D

from Microsoft.FSharp.Collections
val zeroCreate : length1:int -> length2:int -> 'T [,]
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
val mutable k : int
val i : int32
val j : int32
val toRow : a:'t array -> 't List2D.list2d
val a : 't array
type 'T array = 'T []
module Array

from Microsoft.FSharp.Collections
val rev : array:'T [] -> 'T []
val fold : folder:('State -> 'T -> 'State) -> state:'State -> array:'T [] -> 'State
val acc : 't List2D.list2d
val el : 't
module List2D

from Script
union case List2D.list2d.B: 't List2D.list2d * 't List2D.list2d -> 't List2D.list2d
union case List2D.list2d.E: 't -> 't List2D.list2d
union case List2D.list2d.Empty: 't List2D.list2d
val toMatrix : a:'t [,] -> 't List2D.list2d
val a : 't [,]
val s : seq<'t List2D.list2d>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>
val i : int
val length2 : array:'T [,] -> int
module Seq

from Microsoft.FSharp.Collections
val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State
val r : 't List2D.list2d
union case List2D.list2d.A: 't List2D.list2d * 't List2D.list2d -> 't List2D.list2d
val b : int List2D.list2d
val map : f:('a -> 'b) -> _arg1:'a List2D.list2d -> 'b List2D.list2d


 <summary>
 list2d map: apply transformation to each element of list2d
 </summary>
 <param name="f">transformation</param>
val e : int
val listrows : M:'a List2D.list2d -> 'a list list


 <summary>
 List of list2d rows
 </summary>
 <param name="M">list2d</param>
property List2D.list2d.width: int with get


 <summary>
 list2d width: number of B
 </summary>
val sum : (int List2D.list2d -> int)


 <summary>
 list2d sum: matrix total
 </summary>
Raw view Test code New version

More information

Link:http://fssnip.net/80h
Posted:3 years ago
Author:Pavel Tatarintsev
Tags: custom operator , data structure , function composition , recursion

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.