-- Queens with set functions
import SetFunctions
insert x [] = [x]
insert x (y:ys) = x:y:ys ? y:insert x ys
perm [] = []
perm (x:xs) = insert x (perm xs)
list n m = if n==m then [m]
else n : list (n+1) m
queens n = safe (perm (list 1 n))
safe p | isEmpty (set1 unsafe p) = p
unsafe xs = capture (membersWithDeltaDemand xs)
capture (i,lenZ,j) | abs (i-j)-1 == lenZ = success
abs i = if i<0 then 0-i else i
memberWithRest :: [a] -> (a,[a])
memberWithRest (x:xs) = (x,xs) ? memberWithRest xs
memberWithIndex :: [a] -> (a,Int)
memberWithIndex xs = memberWithIndex' 0 xs
memberWithIndex' i (x:xs) = (x,i) ? memberWithIndex' (i+1) xs
-- slow due to copied non-determinism
membersWithDeltaWhere :: [Int] -> (Int,Int,Int)
membersWithDeltaWhere l = (x,i,y)
where (x,xs) = memberWithRest l
(y,i) = memberWithIndex xs
-- fast due to strict evaluation by case
membersWithDeltaCase :: [a] -> (a,Int,a)
membersWithDeltaCase l =
case memberWithRest l of
(x,xs) -> case memberWithIndex xs of
(y,i) -> (x,i,y)
-- this version will be fast after demand analysis
-- (since the current analysis is not general enough, we add a struict
-- assertion on the computed values to enforce more demand)
membersWithDeltaDemand l | x+i+y>0 = (x,i,y)
where (x,xs) = memberWithRest l
(y,i) = memberWithIndex xs
{-
What's necessary to transform membersWithDeltaWhere into membersWithDeltaCase?
Analyze "result demand" of each operation:
- if unsafe should compute some hnf, capture has to compute some hnf
- if capture should compute some hnf, membersWithDeltaWhere has to compute
a partial value (*,*,*) (since capture is strict in this partial value)
- if membersWithDeltaWhere should compute (*,*,*), (y,i) and consequently (x,xs)
has to be computed --> replace where by case (or "strict where")!
Desired implementation of membersWithDeltaWhere:
membersWithDeltaWhere x1 =
(\x2 ->
let x3 = membersWithDelta'_dot___hash_selFP5_hash_x x2
x4 = membersWithDelta'_dot___hash_selFP6_hash_xs x2
in (\x5 ->
let x6 = membersWithDelta'_dot___hash_selFP3_hash_y x5
x7 = membersWithDelta'_dot___hash_selFP4_hash_i x5
in (x3,x7,x6))
$! (memberWithIndex x4))
$! (memberWithRest x1)
-}