[clean-list] unique arrays in unique records

Diederik van Arkel dvanarkel at mac.com
Fri Mar 31 18:44:49 MEST 2006


On Mar 31, 2006, at 5:19 PM, valery at freesurf.fr wrote:

> I am struggling with uniqueness typing (again).
>
> My goal is ultimately to write a search algorithm (alpha-beta, etc.) 
> for a
> board game. Since the board is only slightly altered by each move, I 
> dont
> want to allocate a full board each time, so it is unique.
>
> The state of the search is stored in a unique record, which contains,
> among other things, a unique array representing the board. My attemp to
> update the array is bellow (function seek), but it is rejected :
> Uniqueness error [knight.icl,13,seek]: "board" demanded attribute 
> cannot
> be offered by shared object
>
> How to update a unique array in a record ?
>
> Start = solutions 2
>
> :: Board :== {#Int}
> :: *Seeker = { board :: *Board, wanted :: !Int, found :: [Board]}
>
> solutions :: Int -> [Board]
> solutions n = (foldl seek seeker moves).found
> where
> 	seek :: Seeker Int -> Seeker // line 13 is here
> 	seek s=:{wanted=0} _ = s
> 	seek s=:{board = b, wanted = w, found = f} i
> 	= { s
> 	  & board = { b & [i] = w }
> 	  , wanted = w - 1
> 	  , found = [{b.[i] \\ i <-: b} : f]
> 	  }
> 	seeker = { board = {i \\ i <- [0 .. n * n - 1]}, wanted = 0, found
> = [] }
> 	moves = [0..n]
>

Yeah, this is because you have multiple refererence to Board b in the 
second
seek alternative, eg in the definition of the board field and in the 
definition
of the found field. The references in the found field are particularly 
nasty
bexause it is a lazy list you are building here.

Using a head and tail strict list for your found boards enables you to 
fix this
(I would have expected head strict to have been enough here):

module valery2

import StdEnv

Start = solutions 2

:: Board :== {#Int}
:: *Seeker = { board :: *Board, wanted :: !Int, found :: [!Board!]}

solutions :: Int -> [!Board!]
solutions n = (foldl seek seeker moves).found
where
	seek :: Seeker Int -> Seeker // line 13 is here
	seek s=:{wanted=0} _ = s
	seek s=:{board = b, wanted = w, found = f} i
		#! found = [!{b.[i] \\ i <-: b} : f!]
		= { s
		  & board = { b & [i] = w }
		  , wanted = w - 1
		  , found = found
		  }

	seeker = { board = {i \\ i <- [0 .. n * n - 1]}, wanted = 0, found = 
[!!] }
	moves = [0..n]

Regards,

Diederik van Arkel



More information about the clean-list mailing list