[clean-list] "dummies guide" to structuring a program for uniqueness typing

[Diederik van Arkel]

On Aug 11, 2005, at 2:38 AM, Isaac Gouy wrote:

> Hi Diederik
>
>> in word-frequency change
>>          ht_buckets_to_list :: *[!Item a!] [Item a] -> [Item a]
>> to
>>          ht_buckets_to_list :: .[!Item a!] [Item a] -> [Item a]
>
> That fixed the problem, but how can we describe this bug in a way that
> someone like me can look through our code and see if we're making a
> similar mistake?
>
>
>> And for nbody look at my attached version where I think I was playing
>
>> with some other aspect but which compiles successfully with 2.1.1
>
> Compiled, and gave the correct answer - the fix will appear on the
> website once we start timing again.
>
>
>> For spectral norm if you could show your code I can probably resolve
>
>> the error for you.
>
> This is how I'd left it-
>
>
> module spectralnorm
> import StdEnv, StdArrayExtensions
>
> Start = AtAv n u v
>    where
>    n = 100
>    u = createUnboxedRealArr n 1.0
>    v = createUnboxedRealArr n 0.0
>
> /*
> Start = eigenvalue n (powerMethod 10 n (u,v))
>    where
>    n = 2
>    u = createUnboxedRealArr n 1.0
>    v = createUnboxedRealArr n 0.0
>
>
> eigenvalue n (u,v) = sqrt(vBv/vv)
>    where
>    vBv = asum {a*b \\ a <-: u & b <-: v}
>    vv = asum {a*a \\ a <-: v}
> */
>
>
> powerMethod 0 n (u,v) = (u,v)
> powerMethod step n (u,v)
>    # (u,v) = AtAv n u v
>    # (u,v) = AtAv n v u
>    = powerMethod (step-1) n (u,v)
>
> A i j = 1.0 / toReal ((i+j)*(i+j+1)/2 +i+1)
>
> Av n v a = aloop (n-1) (n-1) v a
> 	where
> 	aloop n i v a
> 	  | i>=0 = aloop n (i-1) v {a&[i] = avsum i n v 0.0}
> 	         = a
> 	
> 	avsum i j v x
> 	  | j>=0 = avsum i (j-1) v (x+((A i j)*v.[j]))
> 	         = x
>
> Atv n v a = aloop (n-1) (n-1) v a
> 	where
> 	aloop n i v a
> 	  | i>=0 = aloop n (i-1) v {a&[i] = atvsum i n v 0.0}
> 	         = a
> 	
> 	atvsum i j v x
> 	  | j>=0 = atvsum i (j-1) v (x+((A j i)*v.[j]))
> 	         = x
>
> AtAv n v a = (u, Atv n u a)
>    where u = Av n v (createUnboxedRealArr n 0.0)
>

AtAv n v a = (u1, Atv n u2 a)
    where
    u = Av n v (createUnboxedRealArr n 0.0)
    (u1,u2)	= dupArray n u

dupArray :: !Int !*{#Real} -> (!.{#Real},!*{#Real})
dupArray n u
	# v	= createUnboxedRealArr n 0.0
	= copy 0 n u v
	where
	copy :: !Int !Int !*{#Real} !*{#Real} -> (!.{#Real},!*{#Real})
	copy i n u v
		| i >= n	= (v,u)
		#! v	= {v & [i] = u.[i]}
		= copy (i+1) n u v

I usually add explicit types to narrow down a problem like this.
Here the {a & [i] = xxx} expression forces the array to be unique. By
adding explicit types I can then track down the location where this
uniqueness requirement is not satisfied.

Regards,

Diederik van Arkel