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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Don Stewart-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Alexander Solla-2

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?

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Don Stewart-2
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
Reply | Threaded
Open this post in threaded view
|

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

Roman Leshchinskiy
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
Reply | Threaded
Open this post in threaded view
|

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

Alexander Solla-2
In reply to this post by Don Stewart-2

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. ;-)
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Henning Thielemann
In reply to this post by Don Stewart-2

On Sun, 7 Mar 2010, Edgar Z. Alvarenga wrote:

> 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))

Since I liked to have both element-wise lazy construction and packed data,
I created a data-structure for that purpose:
   http://code.haskell.org/storablevector/Data/StorableVector/Cursor.hs
However, those vectors/arrays are finite, but could be extended to a
chunky infinite structure.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe