import SetFunctions import Integer(abs) ------------------------------------------------------------------------- -- Simple test for set functions coin = 0 ? 1 bigCoin = 2 ? 4 f x = coin + x main1 = foldValues (+) 0 (set1 f bigCoin) --> 5 or 9 ------------------------------------------------------------------------- -- Specification of shortest graphs with set functions -- The graph nodes: data Node = A | B | C | D | E -- The directed edges are defined as a non-deterministic successor operation: succ :: Node -> Node succ A = B succ A = C succ B = A succ B = C succ B = D succ C = D succ C = E succ D = E succ E = C -- A constrained constructor to construct non-cyclic paths: consNoCycle :: Node -> [Node] -> [Node] consNoCycle n p | all (n /=) p = n:p -- Extend a non-empty path to a given node: extendPath :: Node -> [Node] -> [Node] extendPath target (n:p) = if target==n then reverse (n:p) else extendPath target (consNoCycle (succ n) (n:p)) -- Returns a path from one node to another. pathFromTo :: Node -> Node -> [Node] pathFromTo n1 n2 = extendPath n2 [n1] -- Returns a shortest path from one node to another. -- Implemented by selecting the shortest path from all pathes. shortestPath :: Node -> Node -> [Node] shortestPath n1 n2 = minValue shorter (set2 pathFromTo n1 n2) where shorter p1 p2 = length p1 <= length p2 ---------------------------------------------------------------------- -- Definition of n-queens with set functions perm [] = [] perm (x:xs) = insert x (perm xs) where insert z ys = z : ys insert z (y:ys) = y : insert z ys queens n | isEmpty ((set1 unsafe) p) = p where p = perm [1..n] unsafe xs | xs =:= _++[x]++y++[z]++_ = abs (x-z) =:= length y + 1 where x,y,z free -- a bit more elegant with functional patterns: --unsafe (_++[x]++y++[z]++_) = abs (x-z) =:= length y + 1