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: <<loop>> -- Don
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.
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?
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
On Mar 7, 2010, at 5:22 PM, Don Stewart wrote:
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 :-)
Yeah, fair enough. I studied mathematics, not Haskell's Data.* hierarchy. The potential for confusion is pretty strong, especially since Haskell uses other mathematical terms (functor, monad, etc) with the mathematical meaning in mind. Then again, Haskell type classes are not proper classes -- they're constructible sets of constructible types, at best. Integrals are integer-like, and Haskell derivatives are programming languages like Adga. ;-)
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
participants (3)
-
Alexander Solla -
Don Stewart -
Roman Leshchinskiy