Suffix Tree
Does anybody know of a suffix tree implementation for Haskell? Are there algorithms for a (lazy) functional setting? My reference is Dan Gusfield: "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology". Thanks, Markus -- Markus Schnell Infineon Technologies AG, CPR ET Tel +49 (89) 234-20875 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: foldr in terms of map
Hal Daume wrote:
> > map f = foldr ((:) . f) []
>
> as I understand it, this is essentially because foldr encapsulates all
> primitive recursive functions and since map is primitive recursive, we
> can implement it in terms of a fold.
>
> one thing that is interesting to note is that if we are also given
> references, a function to sequence monadic actions ('sequence_') and
> reverse, we can write foldr in terms of map
Yeah, but given that sequence_ is essentially the direct monadic
translation of fold:
sequence_:: Monad m => [m a] -> m ()
sequence_ = foldr (>>) (return ())
that might be considered cheating (i.e. we can implement fold using
only map and fold, although the fold can be "disguised").
> now, when we're in the IO monad, the difference between the real foldr
> and the simulated one is that the simulated one cannot deal with
> infinite inputs. for instance:
>
> > head $ foldr (:) [] [1..]
>
> should return 1, which it does for the real version. the simulated one
> hangs.
>
> one might like to attribute this to the fact that IO is a strict monad,
Yep.
> but that doesn't seem to be all -- we would also need to be able to read
> and write references lazily in order to get this to work completely.
Which is basically the same thing as "IO is strict".
> Q1: is this correct? is there a way to "fix" the above definition or to
> use a different monad to get laziness? i think not, but can't prove it.
However the monad is defined, sequence_ has to process the entire list
before anything can be determined about the result. The entire result
of (>>) depends upon both arguments, whereas you can deduce the head
of the result of (:) based solely upon the first argument.
> now, if we just limit ourselves to finite inputs, things look a lot
> better. however, this brings up really the main question i have.
>
> foldr (in its original form) is in some sense quintessentially(sp?) PR
> on lists, whereas map is not. however, it seems that the combination
> map+rsequence_+references is enough to give you full PR power.
As mentioned above, sequence_ etc are essentially the embodiment of
primitive recursion.
> what more can we say about this? clearly references play the largest
> role here,
I disagree; sequencing is the key factor. The core issue is that each
recursive call receives a parameter which depends upon all previous
steps, unlike map, where each step is independent (for a monadic
implementation, this actually occurs in the "run" operation, e.g.
runST).
An implementation using a simple state-transformer monad (s -> (a, s))
wouldn't look significantly different to one using IORef/STRef.
> but it also seems impossible to remove this dependence on the
> sequencing operation.
Yep.
--
Glynn Clements <[EMAIL PROTECTED]>
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
RE: foldr in terms of map
Hi, quick reply :)...i've reordered some of what you've said (i hope you don't mind!) > However the monad is defined, sequence_ has to process the entire list > before anything can be determined about the result. The entire result > of (>>) depends upon both arguments, whereas you can deduce the head > of the result of (:) based solely upon the first argument. yes, thanks. > Yeah, but given that sequence_ is essentially the direct monadic > translation of fold: > that might be considered cheating (i.e. we can implement fold using > only map and fold, although the fold can be "disguised"). > > As mentioned above, sequence_ etc are essentially the embodiment of > primitive recursion. Is this true in the same way that the statement 'foldr' is the embodiment of PR is true? That is, can you write foldr in terms of sequence_? It doesn't seem possible: you seem to also need the map in order to get the list lifted into the monadic world and I don't think you can even write map in terms of sequence_ (am I wrong?). > An implementation using a simple state-transformer monad (s -> (a, s)) > wouldn't look significantly different to one using IORef/STRef. True :). Thanks for your comments! - Hal ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Ledit (was Re: [Caml-list] how to use a module) (fwd)
There was some discussion about something like this a while ago...would this solve our problems? -- Hal Daume III | [EMAIL PROTECTED] "Arrest this man, he talks in maths." | www.isi.edu/~hdaume -- Forwarded message -- Date: Tue, 1 Jul 2003 14:49:22 -0400 From: Neel Krishnaswami <[EMAIL PROTECTED]> To: Matt Gushee <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] Subject: Re: Ledit (was Re: [Caml-list] how to use a module) Matt Gushee writes: > > Okay, then, I have some questions about ledit: > > How do you use it? I have actually tried ledit 2 or 3 times, but if > I invoke the 'ledit' executable that is created, e.g. > > $ ./ledit > > I get ... something ... some sort of shell-like environment, I > guess. But all it does is echo whatever I type. And when I read your > post, I downloaded it again to be sure, but the same thing happened > again. I also tried making a custom toplevel with ledit, but the > result seems to be identical to the plain ledit executable. Do this $ ledit ocaml in order to get line editing in the ocaml toplevel. The really cool thing about ledit is that it adds line editing to *any* program. -- Neel Krishnaswami [EMAIL PROTECTED] --- To unsubscribe, mail [EMAIL PROTECTED] Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Suffix Tree
G'day.
On Tue, Jul 01, 2003 at 10:02:36AM +0200, [EMAIL PROTECTED] wrote:
> Does anybody know of a suffix tree implementation
> for Haskell? Are there algorithms for a (lazy) functional
> setting?
Yes. Take a look here:
http://www.techfak.uni-bielefeld.de/~kurtz/publications.html
The second paper down in particular ("A Comparison of Imperative and
Purely Functional Suffix Tree Constructions") develops an efficient
implementation in Haskell. There are some more recent papers also
there which may be of use to you as well.
Cheers,
Andrew Bromage
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
