3 people like it.

DSL for detecting patterns in 2D

A simple domain specific langauge (DSL) that can be used to specify and recognize patterrns in 2D arrays. A pattern is defined by composing primitive checks, rotating and translating patterns. See also: http://t.co/6Poty4FL

Implementation of the DSL

 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: 
/// A type that represents a function that test
/// whether an array contains some pattern at a 
/// specified location. It gets the location to 
/// test & the array as arguments and returns bool.
type ShapeDetector = SD of (int -> int -> int[,] -> bool)

/// A primitive that tests whether the value at the
/// current location contains a value 'v'
let equals v = SD (fun x y arr -> arr.[x,y] = v)

/// A combinator that takes 'ShapeDetector' and 
/// creates a new one that returns 'def' when 
/// accessing outside of the array bounds
let border def (SD f) = SD (fun x y arr -> 
  if x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1) 
  then def else f x y arr)

/// A combinator that calls a given ShapeDetector
/// at a location specified by offset dx, dy
let around (dx, dy) (SD f) = SD (fun x y arr ->
  f (x + dx) (y + dy) arr)

/// A combinator that takes a ShapeDetector and
/// builds a new one, which is rotated by 90 degrees
let rotate (SD f) = SD (fun x y arr ->
  f -y x arr)

/// Creates a shape detector that succeeds only
/// when both of the arguments succeed.
let (<&>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr && f2 x y arr)

/// Creates a shape detector that succeeds 
/// when either of the arguments succeed.
let (<|>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr || f2 x y arr)

Sample pattern detector

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
// We want to detect patterns that look like this
// (with any rotation in any place of an array):
// 
//   X - -
//   - X X
//

// Create a detector that tests if a location
// contains 1 and returns 'false' when out of range
let one = border false (equals 1)

// A shape detector for your pattern
let pattern = 
  around (0, 0) one <&> around (1, 0) one <&> 
  around (-1, 1) one

// Test pattern with any rotation: Combine 
// 4 possible rotations with logical or.
let any = 
  pattern <|> rotate pattern <|> 
  rotate (rotate pattern) <|> 
  rotate (rotate (rotate pattern))

Run the pattern detector on a sample input

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
// Create a 2D array as a sample input
let inp = 
  array2D [ [ 0; 0; 1 ]
            [ 0; 1; 0 ]
            [ 0; 1; 0 ] ]

// Get the underlying function and run it
// for all possible indices in the array
let (SD f) = any
for x in 0 .. 2 do
  for y in 0 .. 2 do
    printfn "%A %A" (x, y) (f x y inp)
union case ShapeDetector.SD: (int -> int -> int [,] -> bool) -> ShapeDetector
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

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

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
val equals : v:int -> ShapeDetector

Full name: Script.equals


 A primitive that tests whether the value at the
 current location contains a value 'v'
val v : int
val x : int
val y : int
val arr : int [,]
val border : def:bool -> ShapeDetector -> ShapeDetector

Full name: Script.border


 A combinator that takes 'ShapeDetector' and
 creates a new one that returns 'def' when
 accessing outside of the array bounds
val def : bool
val f : (int -> int -> int [,] -> bool)
System.Array.GetLength(dimension: int) : int
val around : dx:int * dy:int -> ShapeDetector -> ShapeDetector

Full name: Script.around


 A combinator that calls a given ShapeDetector
 at a location specified by offset dx, dy
val dx : int
val dy : int
val rotate : ShapeDetector -> ShapeDetector

Full name: Script.rotate


 A combinator that takes a ShapeDetector and
 builds a new one, which is rotated by 90 degrees
val f1 : (int -> int -> int [,] -> bool)
val f2 : (int -> int -> int [,] -> bool)
val one : ShapeDetector

Full name: Script.one
val pattern : ShapeDetector

Full name: Script.pattern
val any : ShapeDetector

Full name: Script.any
val inp : int [,]

Full name: Script.inp
val array2D : rows:seq<#seq<'T>> -> 'T [,]

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.array2D
val f : (int -> int -> int [,] -> bool)

Full name: Script.f
val x : int32
val y : int32
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view Test code New version

More information

Link:http://fssnip.net/dI
Posted:12 years ago
Author:Tomas Petricek
Tags: dsl , stackoverflow , introduction , pattern matching , array2d