Re: Haskell Digest, Vol 31, Issue 15

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

Re: Haskell Digest, Vol 31, Issue 15

Paul Johnson-2
"minh thu" <[hidden email]> wrote:

>2006/3/15, Duncan Coutts <[hidden email]>:
>  
>
>>On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
>>    
>>
>>>You can also use laziness (untested!):
>>>
>>>data DLink a = (DLink a) a (DLink a) | Nil
>>>
>>>test = d1
>>>  where d1 = Nil 5 d2
>>>            d2 = d1 6 Nil
>>>
>>>test here is a linked list containing 5 and the next node containing
>>>6. Both nodes have references to the next and previous links (wich is
>>>Nil at the ends). The magic here is laziness. You reference d2 in the
>>>definition for d1 and d1 in the definition for d2. It gets sort of
>>>clumsy to work with, though. You're probably better off using STRefs
>>>(for example) if you really need that type of data structures...
>>>      
>>>
>>I wrote a talk once on this topic:
>>http://web.comlab.ox.ac.uk/oucl/work/duncan.coutts/papers/recursive_data_structures_in_haskell.pdf
>>
>>Duncan
>>    
>>
>thanks, but I cannot construct the whole sturcture in one time (i need
>incremental update).
>  
>
You might also go back and think about why you needed that double linked
list in the first place.  Many things that require complicated list
structures in C are better represented as compositions of functions.  
The simplest example is StringS in the Standard Prelude, which avoids
O(n^2) behaviour in list concatenation by composing functions instead.  
Similarly you might find that by representing your data structure as the
composition of the functions needed to build it you can defer creation
of the actual structure to the point at which it gets read.  Then all
the closures get evaluated, but the evaluated stuff stays around and
acts as the foundation for subsequent updates.  It all depends on what
you want to do.

I suggest reading Chris Okasaki (sp?) on the subject.

Paul.

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

Re: Re: Haskell Digest, Vol 31, Issue 15

Vo Minh Thu
2006/3/15, Paul Johnson <[hidden email]>:

> "minh thu" <[hidden email]> wrote:
>
> >2006/3/15, Duncan Coutts <[hidden email]>:
> >
> >
> >>On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
> >>
> >>
> >>>You can also use laziness (untested!):
> >>>
> >>>data DLink a = (DLink a) a (DLink a) | Nil
> >>>
> >>>test = d1
> >>>  where d1 = Nil 5 d2
> >>>            d2 = d1 6 Nil
> >>>
> >>>test here is a linked list containing 5 and the next node containing
> >>>6. Both nodes have references to the next and previous links (wich is
> >>>Nil at the ends). The magic here is laziness. You reference d2 in the
> >>>definition for d1 and d1 in the definition for d2. It gets sort of
> >>>clumsy to work with, though. You're probably better off using STRefs
> >>>(for example) if you really need that type of data structures...
> >>>
> >>>
> >>I wrote a talk once on this topic:
> >>http://web.comlab.ox.ac.uk/oucl/work/duncan.coutts/papers/recursive_data_structures_in_haskell.pdf
> >>
> >>Duncan
> >>
> >>
> >thanks, but I cannot construct the whole sturcture in one time (i need
> >incremental update).
> >
> >
> You might also go back and think about why you needed that double linked
> list in the first place.  Many things that require complicated list
> structures in C are better represented as compositions of functions.
> The simplest example is StringS in the Standard Prelude, which avoids
> O(n^2) behaviour in list concatenation by composing functions instead.
> Similarly you might find that by representing your data structure as the
> composition of the functions needed to build it you can defer creation
> of the actual structure to the point at which it gets read.  Then all
> the closures get evaluated, but the evaluated stuff stays around and
> acts as the foundation for subsequent updates.  It all depends on what
> you want to do.
>
hi,
to be clear, the data structure i'm thinking of is the "half edge" or
"winged edge" : data structures to represent a 3d mesh in 3d modeling
apps (thus, a constraint is that it can handle lot of data and fast
updates).

the idea of creating the data structure in plain c (and maybe the
basic functions) and then use it (them) in haskell is bad ?

thanks,
vo minh thu
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Re: Haskell Digest, Vol 31, Issue 15

Jared Updike
General question to the list:
(Q)  Are there any data structures in Haskell similar to C++/STL
vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g.
List<int>)? These data structures grow automatically as you add
elements to them (but in large chunks, not one node at a time). This
data structure (if it exists in Haskell) would run inside a monad (ST
and/or IO) and it would automaticly resize when needed, but would be
more or less like a mutable array except you can add new elements to
the end of it without reallocating an entire array of n+1 elements...

> hi,
> to be clear, the data structure i'm thinking of is the "half edge" or
> "winged edge" : data structures to represent a 3d mesh in 3d modeling
> apps (thus, a constraint is that it can handle lot of data and fast
> updates).

Instead of pointers I would use integer offsets into an array of
vertices. Unboxed arrays should help here. (I know when I coded a
winged edge library in C++ I used indices to vertices instead of
pointers, I think...) You can update mutable arrays in place (inside
the ST or IO monad, of course), though I haven't had time to play with
this:
   http://haskell.org/haskellwiki/Arrays
This would be a lot more effective than lists or even doubly linked
lists (mutable array access time = O(1), update time = O(1)). You
could accumulate your vertices into a list and then freeze it into an
array. If you need to add vertices to your array after you create it,
you will need a data type like I mentioned at the (Q) above (if it
exists).

> the idea of creating the data structure in plain c (and maybe the
> basic functions) and then use it (them) in haskell is bad ?

This might be possible, but I don't think that C has the right type of
data structure, either (though certainly you could create it). Ideally
you want something like C++ vectors or C# generic Lists if you need
the ability to augment it.

If you make the datastructures and functions in C you'd still have to
wrap these functions in a monad like IO to make it safe (Which the
Array libs do ... if they are the right datastructure for you.) but
that's probably only a good idea if you can't find the right
datastruct in Haskell.

  Jared.
--
http://www.updike.org/~jared/
reverse ")-:"
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

dynamic arrays

Bulat Ziganshin-2
Hello Jared,

Thursday, March 16, 2006, 11:35:24 PM, you wrote:

JU> General question to the list:
JU> (Q)  Are there any data structures in Haskell similar to C++/STL
JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g.
JU> List<int>)? These data structures grow automatically as you add
JU> elements to them (but in large chunks, not one node at a time). This
JU> data structure (if it exists in Haskell) would run inside a monad (ST
JU> and/or IO) and it would automaticly resize when needed, but would be
JU> more or less like a mutable array except you can add new elements to
JU> the end of it without reallocating an entire array of n+1 elements...

i tried to implement this today :) but there is one problem:

if i have (l,u) - array bounds of type Ix, and i - offending index of
the same type, how can i compute new bounds of array so that it will
grow in large chunks? there is no such computation operations for
Ix type and that is logical - if this array is really a matrix then
it's hard to use the same rules of extending it as for vectors

such computation as (u-l)*2+l is great for integral indexes, but not
for general case. now i plan to use this strategy for all enum types
and just "grow to minimal and maximal indexes actually used" for other
index types


--
Best regards,
 Bulat                            mailto:[hidden email]

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

Re: dynamic arrays

Vo Minh Thu
2006/3/17, Bulat Ziganshin <[hidden email]>:

> Hello Jared,
>
> Thursday, March 16, 2006, 11:35:24 PM, you wrote:
>
> JU> General question to the list:
> JU> (Q)  Are there any data structures in Haskell similar to C++/STL
> JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g.
> JU> List<int>)? These data structures grow automatically as you add
> JU> elements to them (but in large chunks, not one node at a time). This
> JU> data structure (if it exists in Haskell) would run inside a monad (ST
> JU> and/or IO) and it would automaticly resize when needed, but would be
> JU> more or less like a mutable array except you can add new elements to
> JU> the end of it without reallocating an entire array of n+1 elements...
>
> i tried to implement this today [...mail cut here ...]

hello,
when you say you try to implement it, how do you do it ? c -> ffi -> haskell ?

thanks,
minh thu
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: dynamic arrays

Vo Minh Thu
2006/3/17, minh thu <[hidden email]>:

> 2006/3/17, Bulat Ziganshin <[hidden email]>:
> > Hello Jared,
> >
> > Thursday, March 16, 2006, 11:35:24 PM, you wrote:
> >
> > JU> General question to the list:
> > JU> (Q)  Are there any data structures in Haskell similar to C++/STL
> > JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g.
> > JU> List<int>)? These data structures grow automatically as you add
> > JU> elements to them (but in large chunks, not one node at a time). This
> > JU> data structure (if it exists in Haskell) would run inside a monad (ST
> > JU> and/or IO) and it would automaticly resize when needed, but would be
> > JU> more or less like a mutable array except you can add new elements to
> > JU> the end of it without reallocating an entire array of n+1 elements...
> >
> > i tried to implement this today [...mail cut here ...]
>
> hello,
> when you say you try to implement it, how do you do it ? c -> ffi -> haskell ?
>
> thanks,
> minh thu
>
sorry, i have read badly ... it seems you use plain haskell code,
mt
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Re: Haskell Digest, Vol 31, Issue 15

Udo Stenzel
In reply to this post by Vo Minh Thu
minh thu wrote:
> to be clear, the data structure i'm thinking of is the "half edge" or
> "winged edge"

this would involve a cyclic structure, and you want to update that.  I
don't think there's a purely functional way to implement that, and if
there is, it wouldn't allow O(1) modifications.

So it appears, you will have to mangle pointers.  This is indeed
possible, pointers in Haskell are spelled "STRef".


> the idea of creating the data structure in plain c (and maybe the
> basic functions) and then use it (them) in haskell is bad ?

Do you honestly think that C is ever a good idea?  Of course, you can
write the data structure in C, but it will be essentially the same code
you would write in Haskell using STRefs.  Additionally you will get the
usual off-by-one errors, dangling pointers and the ever helpful error
message "killed by SEGSEGV".


Udo.
--
<Alanna> Saying that Java is nice because it works on all OS's is
like saying that anal sex is nice because it works on all genders.

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell

signature.asc (196 bytes) Download Attachment