# Re: [Haskell] Recursive definition of fibonacci with Data.Vector Classic List Threaded 6 messages Open this post in threaded view
|

## Re: [Haskell] Recursive definition of fibonacci with Data.Vector

 edgar: > Hello, > > why I can't define a recursive vector using Data.Vector, like in > the example: > > import qualified Data.Vector as V > > let fib = 0 `V.cons` (1 `V.cons` V.zipWith (+) fib (V.tail v)) > There's a typo:   fib = 0 `V.cons` (1 `V.cons` V.zipWith (+) fib (V.tail fib)) Which let's it typecheck. But I don't think this is a sensible use of vectors. In fact, infinite vectors make no sense, as far as I can tell -- these are fundamentally bounded structures.  GHC even optimizes it to:     fib = fib (literally!).     \$ time ./A     A: <> -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Re: [Haskell] Recursive definition of fibonacci with Data.Vector

 On Mar 7, 2010, at 12:56 PM, Don Stewart wrote:In fact, infinite vectors make no sense, as far as I can tell -- theseare fundamentally bounded structures.Fourier analysis?  Functional analysis?  Hamel bases in Real analysis?  There are lots of infinite dimensional vector spaces out there.GHC even optimizes it to:   fib = fibSounds like an implementation bug, not an infinite dimensional vector space bug.  My guess is that strictness is getting in the way, and forcing what would be a lazy call to fib in the corresponding list code -- fib = 0 : 1 : (zipWith (+) fib (tail fib)) -- into a strict one.In fact, I'm pretty sure that's what the problem is:```data Vector a = Vector {-# UNPACK #-} !Int {-# UNPACK #-} !Int {-# UNPACK #-} !(Array a)````The !'s mean "strict" right?`_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Re: [Haskell] Recursive definition of fibonacci with Data.Vector

 ajs: > > On Mar 7, 2010, at 12:56 PM, Don Stewart wrote: > > >     In fact, infinite vectors make no sense, as far as I can tell -- these >     are fundamentally bounded structures. > > > Fourier analysis?  Functional analysis?  Hamel bases in Real analysis?  There > are lots of infinite dimensional vector spaces out there. Sorry for the overloading, I mean 'vector' in the sense of Data.Vector. Being strict in the length, its unclear  to me that you can do much with infinite ones :-) Of course, all the nice optimizations will also work for lazy structures, like lists, but that's a different library. >     GHC even optimizes it to: > >        fib = fib > > Sounds like an implementation bug, not an infinite dimensional vector space > bug.  My guess is that strictness is getting in the way, and forcing what would > be a lazy call to fib in the corresponding list code -- fib = 0 : 1 : (zipWith > (+) fib (tail fib)) -- into a strict one. > > In fact, I'm pretty sure that's what the problem is: > > > data Vector a = Vector {-# UNPACK #-} !Int >                        {-# UNPACK #-} !Int >                        {-# UNPACK #-} !(Array a) > > > The !'s mean "strict" right? That's precisely the right semantics for strict-in-the-length arrays. And it is brilliant that GHC reduces it all down to the minimal possible program that has the same semantics as a non-terminating strict-length infinite array. -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Re: [Haskell] Recursive definition of fibonacci with Data.Vector

 In reply to this post by Alexander Solla-2 On 08/03/2010, at 12:17, Alexander Solla wrote: >> GHC even optimizes it to: >> >>    fib = fib > > Sounds like an implementation bug, not an infinite dimensional vector space bug.  My guess is that strictness is getting in the way, and forcing what would be a lazy call to fib in the corresponding list code -- fib = 0 : 1 : (zipWith (+) fib (tail fib)) -- into a strict one. > > In fact, I'm pretty sure that's what the problem is: > > data Vector a = Vector {-# UNPACK #-} !Int >                        {-# UNPACK #-} !Int >                        {-# UNPACK #-} !(Array a) The problem is that you have to allocate an Array of a specific length when creating a Vector. Arrays are finite by definition. It's not a bug, it's a feature. Note that in the context of package vector, "vector" means a 1-dimensional, 0-indexed array. This is not unusual - see, for instance, the standard C++ library. Roman _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe