[Haskell-cafe] Re: [Haskell] Recursive definition of fibonacci
with Data.Vector
Don Stewart
dons at galois.com
Sun Mar 7 20:22:20 EST 2010
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
More information about the Haskell-Cafe
mailing list