Tagged Questions
9
votes
1answer
207 views
How to define a tree-like DAG in Haskell
How do you define a directed acyclic graph (DAG) (of strings) (with one root) best in Haskell?
I especially need to apply the following two functions on this data structure as fast as possible:
...
2
votes
1answer
148 views
Building a graph from a list of edges
Given a graph datatype as follows:
data Graph = Int :~> [Graph]
infixr :~>
and a list of edges like this:
edges = [(10,1), (10,5), (1,2), (2,3), (5,6), (5,9), (9,8)]
What is the function ...
12
votes
2answers
220 views
QuickCheck: Arbitrary instances of nested data structures that generate balanced specimens
tl;dr: how do you write instances of Arbitrary that don't explode if your data type allows for way too much nesting? And how would you guarantee these instances produce truly random specimens of your ...
3
votes
3answers
82 views
Building a tree from database rows
I need to build a tree from database rows. To be more specific I have a table wich contains the chart of accounts.
Instead of querying the table recursively I want to load all the tables' ...
6
votes
1answer
163 views
Can we think of immutable lists as a dual to trees?
I might draw a list of words like:
this -> is -> a -> test
and then through sharing, I might draw two lists as:
this -> is -> a -> test
^
...
17
votes
2answers
650 views
Internal representation of Haskell lists?
Haskell supports some basic operations for recursing through lists, like head, tail, init and last. I'm wondering, internally, how Haskell is representing its list data? If it's a singly-linked list, ...
4
votes
3answers
363 views
Remove elements during infinite sequence generation
I found a great haskell solution (source) for generating a Hofstadter sequence:
hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..]
Now, I am trying to write such a solution ...
0
votes
2answers
210 views
What haskell data structure to store mutable tree
I was thinking about writing a browser in haskell. A central data structure will be a mutable tree representing the document. Apart from using a tree composing entirely of iorefs, is there a better ...
2
votes
2answers
131 views
Is there a stricter Data.Sequence?
The following example shows a problem that we have with Data.Sequence:
{-# LANGUAGE BangPatterns #-}
module Main where
import qualified Data.Sequence as S
import Data.Sequence ((|>), ViewL(..))
...
7
votes
3answers
253 views
What is the most efficient implementation of arrays with functional updates?
I need an array-like data structure with the fastest possible functional update. I've seen a few different implementation of flexible arrays that provide me with this property (Braun, Random Access ...
7
votes
0answers
188 views
What's the difference between content in book (1999) and thesis (1996) for Chris Okasaki — Purely Functional Data Structures [closed]
I want to read Purely Functional Data Structure work. I've easily found thesis (which is freely available, 1996), but see that there's a book available also (1999). So I'd like to know how big is the ...
0
votes
1answer
206 views
Implementing Inductive Graphs in Haskell
I'd like to give Martin Erwing's inductive graph implementation a shot. However, I am still new to Haskell's type system, specifically when it comes to defining abstract data types. I was hoping ...
4
votes
2answers
159 views
freezing haskell STrefs
I would like to implement a Doubly Connected Edge List data structure for use in Haskell. This data structure is used to manage the topology of an arrangement of lines in a plane, and contains ...
16
votes
1answer
322 views
How to create a diff of two complex data structures?
Problem specification:
I am currently searching for a elegant and/but efficient solution to a problem that i guess is quite common. Consider the following situation:
I defined a fileformat based on ...
1
vote
2answers
159 views
Haskell representation for spider solitaire tableau
I am working on a Haskell implementation of a Spider Solitaire player, both as an exercise in learning Haskell and trying to find a good player algorithm.
I am looking for an efficient representation ...
34
votes
8answers
3k views
Purely functional data structures for text editors
What would be good purely functional data structures for text editors? I want to be able to insert single characters into the text and delete single characters from the text with acceptable ...
8
votes
1answer
418 views
Zipper data structure for graphical model editor
I'm writing a graphical editor for a "model" (i.e. a collection of boxes and lines with some kind of semantics, such as UML, the details of which don't matter here). So I want to have a data structure ...
11
votes
5answers
233 views
When to expose constructors of a data type when designing data structures?
When designing data structures in functional languages there are 2 options:
Expose their constructors and pattern match on them.
Hide their constructors and use higher-level functions to examine the ...
4
votes
1answer
99 views
How could I best express this relationship in my Traveller implementation
I'm putting together a Traveller implementation, and have begun by defining my data structures. I ran into a problem when trying to define a Ship.
I began with some simple data definitions.
data Ship ...
10
votes
3answers
608 views
Why aren't FingerTrees used enough to have a stable implementation?
A while ago, I ran across an article on FingerTrees (See Also an accompanying Stack Overflow Question) and filed the idea away. I have finally found a reason to make use of them.
My problem is that ...
11
votes
1answer
588 views
Intelligent purely functional sets
Set computations composed of unions, intersections and differences can often be expressed in many different ways. Are there any theories or concrete implementations that try to minimize the amount of ...
19
votes
4answers
1k views
What are lenses used/useful for?
I can't seem to find any explanation of what lenses are used for in practical examples. This short paragraph from the Hackage page is the closest I've found:
This modules provides a convienient ...
8
votes
2answers
460 views
efficient functional data structure for finite bijections
I'm looking for a functional data structure that represents finite bijections between two types, that is space-efficient and time-efficient.
For instance, I'd be happy if, considering a bijection f ...
5
votes
4answers
539 views
Data structure to represent automata
I'm currently trying to come up with a data structure that fits the needs of two automata learning algorithms I'd like to implement in Haskell: RPNI and EDSM.
Intuitively, something close to what ...
5
votes
3answers
540 views
Haskell: Datastruture with O(1) append and O(1) indexing?
I am looking for a data structure in Haskell that supports both fast indexing and fast append. This is for a memoization problem which arises from recursion.
From the way vectors work in c++ (which ...
22
votes
1answer
493 views
Avoiding IORefs in pure code
I noticed that Data.UnionFind uses the IO monad to provide pointers via IORefs. I imagine everyone happily calls unsafePerformIO when using it locally in pure code, since the data structure is so well ...
6
votes
1answer
236 views
Haskell: list/vector/array performance tuning
I am trying out Haskell to compute partition functions of models in statistical physics. This involves traversing quite large lists of configurations and summing various observables - which I would ...
4
votes
1answer
100 views
Nested UNPACKs in GHC
I often gather multiple values in tuples, since I consider tuples to be the natural type for this. However, tuples are not strict. So consider
data A
data B =
B !A
data C =
C !(B, B)
data ...
1
vote
1answer
159 views
Why does unordered-containers have their own implementation of Array
I'm reading on HAMT's, and looked at a reference implementation in unordered-containers, but noticed that they have their own implementation of arrays. Why is this? Is it for speed? Or is it for some ...
1
vote
1answer
171 views
is “calling functions in data structure” possible in haskell?
i have some functions(charfreq,wordfreq,charcount,wordcount,parerror) and i want to use it in dataStructure with the given string.But how can i do it? I'm trying in these and many way ,but i got all ...
