I'am a little bit confused by the following error messages : \begin{code} import Array type SignalOf = Array Int funcSignal :: (Num a, Num b) => (Int, Int) -> (a -> b) -> SignalOf b funcSignal b f = listArray b [f (fromIntegral k) | k <- range b] instance (Num a) => Num (SignalOf a) where fromInteger k = funcSignal (minB, maxB) (const i) where minB = (minBound :: Int) + 1 maxB = (maxBound :: Int) - 1 i = fromInteger k \end{code} When testing on ghci -> *Main> let x = 1::SignalOf Int Loading package haskell98 ... linking ... done. *Main> bounds x zsh: segmentation fault (core dumped) ghci infArray.hs Is it not possible to define a really huge array ? Fred
On Fri, 2004-12-03 at 13:21 +0100, Fred Nicolier wrote:
I'am a little bit confused by the following error messages :
\begin{code} import Array type SignalOf = Array Int
funcSignal :: (Num a, Num b) => (Int, Int) -> (a -> b) -> SignalOf b funcSignal b f = listArray b [f (fromIntegral k) | k <- range b]
instance (Num a) => Num (SignalOf a) where fromInteger k = funcSignal (minB, maxB) (const i) where minB = (minBound :: Int) + 1 maxB = (maxBound :: Int) - 1 i = fromInteger k \end{code}
When testing on ghci -> *Main> let x = 1::SignalOf Int Loading package haskell98 ... linking ... done. *Main> bounds x zsh: segmentation fault (core dumped) ghci infArray.hs
Is it not possible to define a really huge array ?
No. The array really does get created with that huge number elements. The Haskell Array type is lazy in it's *elements*, not its keys. The underlying implementation something like a C array of pointers to (not necessarily yet evaluated) values. The Array type is just your ordinary O(1) indexable structure. If you want a data structure that works well with sparse keys, you'll need to look beyond the simple Array type. FiniteMap would work fine for this. I can't immediately think of a collection data structure combining O(1) lookup with a sparse key space however - that sounds quite tricky. Duncan
No. The array really does get created with that huge number elements. The Haskell Array type is lazy in it's *elements*, not its keys.
Ok thanks, i understand (my error is that i want lazy datas everywhere !!)
The Array type is just your ordinary O(1) indexable structure. If you want a data structure that works well with sparse keys, you'll need to look beyond the simple Array type. FiniteMap would work fine for this.
My aim is to design signal/image processing code. I dont want efficiency but clarity. I hope to be closer as possible to the "math" defs. By definition a signal is a function from Integer to Nums. So i modify my code as joined. The question is : should i design a class (derived from FinitMap by example) or keep the defined datatype ? Fred ----- ----- import Data.Array -- The general definition of a signal data SignalOn x a = Signal (x, x) (x -> a) -- some constructor (other can be easily defined) funcSignal b f = Signal b f listSignal b l = Signal b ( \k -> l!!(k - fst b) ) arraySignal b a = Signal b (a!) -- a monodimensional signal is just a specialized signal type Signal1dOf a = SignalOn Int a -- an Image is just a specialized signal type ImageOf a = SignalOn (Int, Int) a funcImage :: ((Int, Int), (Int, Int)) -> ((Int, Int) -> a) -> ImageOf a funcImage b f = Signal b f -- some stuff to access the basic properties of a signal values (Signal b f) = [f k | k <- range b] funcOf (Signal _ f) = f bnds (Signal b f) = b (&) (Signal _ f) x = f x instance (Index k, Num a) => Show (SignalOn k a) where show (Signal b f) = "Signal on " ++ show b ++ " = " ++ show ( map f (range b) ) mixWith op (Signal b f) (Signal b' f') = Signal b ( \k -> op (f k) (f' k)) instance (Index k, Eq a) => Eq (SignalOn k a) where x /= y = ( bnds x /= bnds y) || (values x /= values y) instance (Index k) => Functor (SignalOn k) where fmap g (Signal b f) = Signal b (g.f) instance (Num a) => Num (Signal1dOf a) where (+) = mixWith (+) (*) = mixWith (*) signum = fmap signum abs = fmap abs fromInteger k = funcSignal (minB, maxB) (const (fromIntegral k) ) where minB = (minBound :: Int) maxB = (maxBound :: Int) -- Necessary stuff for indexes class (Ix a, Ord a, Show a) => Index a where max2Ix :: a -> a -> a min2Ix :: a -> a -> a ltIx :: a -> a -> Bool lengthIx :: a -> Int add2Ix :: a -> a -> a mul2Ix :: a -> a -> a negIx :: a -> a max2Ix x y = max x y min2Ix x y = min x y ltIx x y = x <= y lengthIx _ = 1 instance Index Int where add2Ix x y = x + y mul2Ix x y = x * y negIx x = -x instance (Index a, Index b) => Index (a,b) where max2Ix (x1,y1) (x2,y2) = (max2Ix x1 x2, max2Ix y1 y2) min2Ix (x1,y1) (x2,y2) = (min2Ix x1 x2, min2Ix y1 y2) ltIx (x1,y1) (x2,y2) = ltIx x1 x2 && ltIx y1 y2 lengthIx _ = 2 add2Ix (x1,y1) (x2,y2) = (add2Ix x1 x2, add2Ix y1 y2) mul2Ix (x1,y1) (x2,y2) = (mul2Ix x1 x2, add2Ix y1 y2) negIx (x,y) = (negIx x, negIx y)
On Sat, 2004-12-04 at 19:12 +0000, Jules Bean wrote:
On 3 Dec 2004, at 19:22, Duncan Coutts wrote:
I can't immediately think of a collection data structure combining O(1) lookup with a sparse key space however - that sounds quite tricky.
Hashtable, surely?
Yes of course - silly me! I forget about hash tables because as a functional programmer I don't use them very often since they need to be used in a monad. I wonder in what situations a purely functional hash table based on DiffArray would perform better than a FiniteMap. Duncan
participants (3)
-
Duncan Coutts -
Fred Nicolier -
Jules Bean