Re: [Haskell-cafe] [GSOC] About "Implementing Maps using generalized tries" project idea

[Jamie Brandon]

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gmap-0.1

Everything in the release is working. There's some fast map/trie
implementations and a bunch of map combinators. In Test.GMap there are
~800 lines of quickcheck properties. The tests use some undocumented
type hackery to allow them to run on any instance of the GMap class.
Some of the strictness invariants demanded by the test suite are not
documented.

There are no real benchmarks. I'm still not even sure how to
effectively benchmark haskell code.

If you want to suggest this as a project for 2009 I think the
priorities should be:
  Documentation + examples (which I'm willing to help with if there is interest)
  Systematic benchmarks
  Integration with the edison api, to encourage a single collection
api on hackage

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Left fold enumerator - a real pearl overlooked?

[Jamie Brandon]

> Can someone point us to some resources about these? I for one have not heard
> of them before

http://okmij.org/ftp/Streams.html#iteratee

is probably the best place to start.

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] A typeclass for Data.Map etc?

[Jamie Brandon]

> Maybe this is of interest:
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gmap

The edison api is much more stable. The gmap api was already in place
when I started working on it but I would prefer to at some point make
it a superset of the edison api. No sense in having more than one map
interface lying around.

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] FP simulators for real-time systems?

[Jamie Brandon]

Opis is an ocaml library for implementing reactive systems where the
same code can either be executed, run in a simulator or used as a
specification in a formal model checker. The model checking is only
possible because referential transparency massively reduces the state
space of the program.

http://perso.eleves.bretagne.ens-cachan.fr/~dagand/opis/

Flask is a similar haskell project which generates code for sensor
networks. I don't know if they've gone as far down the
testing/modelling route.

http://www.eecs.harvard.edu/~mainland/flask/

The general theme is promising - reducing mutable state makes it much
easier to automate reasoning about code.

Jamie


On Mon, Feb 2, 2009 at 6:43 PM, Lee Pike  wrote:
> Hello,
>
> I'm interested to hear if anyone out there has used Haskell (or other
> functional languages for that matter) to build simulators for real-time
> systems.
>
> I'm somewhat familiar with Timber  and similar
> languages for actually constructing real-time systems.  However, I'm more
> interested in documented uses of FP "out-of-the-box"  to build simulators
> and associated test harnesses.
>
> Pointers to published papers are particularly appreciated.
>
> Thanks!
> Lee
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] real haskell difficulties (at least for me)

[Jamie Brandon]

I agree completely. There is not nearly enough documentation on
packaging in haskell and too many hackage packages are broken or do
not install. I know several people are working on improving this but
they seem do be doing so rather quietly. Could someone briefly outline
what improvements are planned and what stage the current work is at? I
remember seeing some demos at anglohaskell during the summer but
nothing since.

Jamie

On Tue, Jan 13, 2009 at 3:33 PM, Regis Saint-Paul
 wrote:
> Hi,
>
> I've seen many times the monad topic coming around on the cafe and plentiful
> tutorials on monads have been published. However, as a complete Haskell
> newbie coming from OOP, I felt monads were not particularly difficult to
> grasp, and very exciting to work with.
>
> During my experiments with Haskell so far, the main problems I kept bumping
> into were not related to the language but to its libraries: their
> compilation and installation. Unfortunately, this topic has not received
> nearly as much attention. I was unable to find a comprehensive tutorial on
> how to deal with the variety of problems I get when trying to install
> Hackage packages. This turned out to be (and still is) THE main source of
> wasted time and headaches. And worse, unlike type problems, these are not
> interesting ones to solve.
>
> Thus, as a beginner, the package management is what is really getting in the
> way of switching to Haskell--not the language. Even books like Real World
> Haskell (otherwise excellent) ignore entirely the topic. Cabal and
> Cabal-install are clearly wonderful applications that make installing most
> packages very straightforward. Unfortunately, whenever this "standard"
> method for package installation fails (or when it is not available as with,
> e.g., gtk2hs), I find myself in complete disarray.
>
> Below are some of the questions and issues I faced regarding package
> management:
>
> - For a number of packages, cabal-install gets stuck and has to be killed. I
> assume this is due to some difficulties in solving the dependencies and it
> is fine, not all can be automated and cabal-install is not responsible for
> poor packages. But the question then becomes what to do from there? Is their
> some method to solve dependencies? How should we proceed to "debug" a
> package installation? How do gurus deal with that? (maybe some less known
> command line arguments? Or ways to figure out the problem and work out its
> solution (cabal-install is silent in such case)? In particular, how to know
> why did cabal get stuck in the first place?
>
> - Some packages on Hackage are reported as not building successfully with
> GHC6.10 (e.g., encoding) while others do not build with 6.8 (e.g., salvia)
> and the later might depend on the former...What is one supposed to do in
> such case? For example, is it an appropriate way to proceed to compile a
> package with one version of GHC and then use the compiled package with
> another version of GHC? Is it safe? What could possibly go wrong? If it is
> the right way to go, how should we setup the two GHC versions? For instance,
> should we have a shared package configuration file and choose through the
> path which GHC is used or is there nicer way to set this up?
>
> - Taking for example the "encoding" package on Hackage. Last time I tried,
> the log was saying it fails to build on GHC 6.10, however, looking inside
> this Hackage log, I could see a successful compilation using "preferred
> versions". So it looks as if the thing can be compiled somehow. What should
> one do with this information? If cabal manages to compile it using this
> method on Hackage, then isn't cabal install just doing it on my disk? Is it
> possible through some command line? Is it possible manually (without
> cabal-install) and, if so, how? (I tried to copy-past the build instruction
> as it appeared on the log...that somehow compiled, but then, I failed to
> figure out how to install...)
>
> - I'm primarily a windows user and lots of my initial struggles probably
> came from that. After many difficulties, I figured out that installing MinGW
> and MSys was *THE* way to get a bit more of the things working. First, a lot
> of time would be saved by just saying clearly on the GHC download page that
> MinGW and MSys are mandatory installation (or even package that with GHC for
> the windows distribution if license allows, who cares the extra few Mb).
> Even if that is not technically exact, i.e., even if ghci and many trivial
> command line programs can work without, MSys and MinGW turn out to be quiet
> necessary whenever trying to install anything producing side effect. Making
> it plain that these two are necessary would real come has a great time
> savers for newbie like me on windows (personal opinion of course). Or, if
> another path exists to go without these two, I'd be very glad to learn.
> Besides, even these tools basic installation is not enough, you need
> automake and various things of the like

Re: [Haskell-cafe] #haskell IRC channel reaches 600 users

[Jamie Brandon]

The haskell community has a well deserved reputation for being one of
the friendliest online communities. Perhaps this would be a good point
to figure out what we're doing right? I'm convinced that part of it is
that offtopic conversation is encouraged through on haskell-cafe,
planet haskell and irc. It makes people seem more human and hence
harder to flame.

Jamie

On Fri, Jan 2, 2009 at 8:27 PM, Don Stewart  wrote:
>
> A small announcement :)
>
> 7 years after its inception, under the guiding hand of Shae Erisson (aka
> shapr), the #haskell IRC channel[1] on freenode has reached 600
> concurrent users! It's now in the top 3 language channels by size.
>
> To chart the growth, we can note that the channel was founded in late
> 2001, and had slow growth till 2006, reaching 200 users in January of
> that year. Since then growth in the user base has been far more rapid,
> reaching 300 users in Dec 2006, 400 users in August 2007, 500 users
> by July 2008, and 600 on January 2, 2009.
>
> This puts the channel at the 7th largest community of the 7000 freenode
> channels, and in the top 3 language communities. For comparision, a
> sample of the state of the other language communities, with comments
> comapred to their status a year ago:
>
>   #php 612
>   #python  604
>
>  > #haskell 602 -- up 4
>
>   ##c++558
>   ##c  506 -- down 1
>   #perl502 -- down 3
>   #ruby-lang   288 -- down
>   #lisp264
>   ##javascript 241
>   #erlang  146 -- unchanged
>   #perl6   129 -- unchanged
>   #scheme  123 -- down
>   #lua 102 -- unchanged
>   #clojure  78
>   #ocaml70 -- unchanged
>
> You can see the growth of the channel over here:
>
>http://haskell.org/haskellwiki/IRC_channel
>
> If you've not dropped by the channel yet, feel free to come and chat,
> and toss around some lambdas! :)
>
> Cheers,
>Don
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] OT: representations for graphs

[Jamie Brandon]

In model checking, transition matrices (ie weighted adjacency
matrices) are often represented by binary decision diagrams. They're a
very compact way of representing sparse or regular vectors/matrices
(where graphs can be thought of as adjacency matrices). Theres some
good lecture notes on them here:

http://web.comlab.ox.ac.uk/teaching/materials08-09/probabilistic/19-symbolic.pdf

If you skip to page 42 theres a table comparing memory use with
traditional sparse representations.

Jamie

On Fri, Dec 19, 2008 at 5:07 PM, Bayley, Alistair
 wrote:
> (OT, but I'm hoping some of you might have some ideas on this anyway...)
>
> I was wondering what alternative representations there are for graphs,
> or maybe if there might be a way to derive one/some from some insightful
> observations. For the purposes of storing and exmaining (querying)
> graphs in an SQL database.
>
> For example, a tree (so, a specialised sub-class of graph) can be
> represented by a three models, that I know of:
>  - adjacency-list (the most common)
>  - materialised-path (a denormalisation of adjacency-list)
>  - nested-sets
>
> Nested-sets (and materialised-path) works for trees because the graph is
>  - directed (so we know which nodes are parents or children)
>  - acyclic (there's a definite root, and leaves)
>  - every child has a single parent (so no diamond shapes - does this
> property have a name?)
>
> Nested-sets works well with SQL databases for querying, at the expense
> of updates. Adjacency-list is easier to update, but some queries suck,
> or are downright impossible in normal SQL.
>
> We can use the adjacency-list model for graphs too, but it has the same
> query deficiencies as for trees. I'd like some sort of alternative to
> adjacency-list, like nested-sets, that would work better for querying at
> the expense of updates.
>
> Alistair
> *
> Confidentiality Note: The information contained in this message,
> and any attachments, may contain confidential and/or privileged
> material. It is intended solely for the person(s) or entity to
> which it is addressed. Any review, retransmission, dissemination,
> or taking of any action in reliance upon this information by
> persons or entities other than the intended recipient(s) is
> prohibited. If you received this in error, please contact the
> sender and delete the material from any computer.
> *
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] pure programs

[Jamie Brandon]

You're essentially describing functional reactive programming. You end
up with the system being described as pure, reactive values and
plugging IO based streams in at the edges.

Have a look at the wiki description
(http://www.haskell.org/haskellwiki/Functional_Reactive_Programming)
and especially the Reactive library
(http://www.haskell.org/haskellwiki/Reactive).

Theres been a fair amount of work on using frp for distributed,
network-orientated systems. Flask
(http://portal.acm.org/citation.cfm?id=1411203.1411251) and Opis
(http://perso.eleves.bretagne.ens-cachan.fr/~dagand/opis/) are
particularly interesting. Opis really shows the value of using pure
functions by allowing the same reactive system to be run in
production, attached to a debugger, run in a step-by-step simulator or
run in a model checker without altering the systems code.

On Wed, Nov 5, 2008 at 12:12 AM, Jason Dusek <[EMAIL PROTECTED]> wrote:
>  Informally, a "pure program" an executable such that the
>  stream of bytes entering it totally determines the stream of
>  bytes leaving it.
>
>  Many useful programs that I would like to write in Haskell
>  don't fall into this category -- for example, network servers
>  -- but a lot of their components do. Can these components can
>  be Haskell functions without IO in their signatures?
>
>  Though that seems reasonable, it is not, in general, true. For
>  example,System.Info.osis generally treated as pure,
>  though it is not. It's not clear to me how to disambiguate
>  these "born again" values from really pure values.
>
> --
> _jsn
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Spine-lazy "multiqueue"

[Jamie Brandon]

>  Ideas for how to make such tries
> composable would encourage me to release a hackage module :-)

Have a look at code.haskell.org/gmap/api - a library for composable
maps. It currently requires huge instances in the name of efficiency
but I hope to improve that over the next couple of months. The basic
idea is pretty simple:

class Map mp k | mp -> k where
  lookup :: k -> mp a -> Maybe a
  etc

data EitherMap mpL mpR kL kR = EitherMap mpL mpR

instance (Map mpL kL, Map mpR kR) => Map (EitherMap mpL mpR kL kR) where
  lookup (Left l) (EitherMap mpL mpR) = lookup l mpL
  lookup (Right r) (EitherMap mpL mpR) = lookup r mpR

The types can get a bit hairy at the moment but using associated types
instead of fundeps will probably improve that.

For lazy spined maps, lookup 'skew binary random access lists' (in
Okaski's book, if you have a copy). You'll get roughly the same
perfomance as a trie over bits but with the advantage that you can
take the tail in constant time. That way, if your keys are time values
(I'm guessing this is related to your frp ideas) you get the same
garbage collection properties as a simple list of [(Time,a)] but you
can still look ahead efficiently.

If you have problems with sparse time values you could compose the
random access list with something else:

data TimeMap mp a = TM (RandList (mp a))

instance (Map mp Integer) => Map (TimeMap mp) Integer where
  lookup k (TM randList) = lookup k (lookup (div k chunkSize) randList)
  etc
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: Red-Blue Stack

[Jamie Brandon]

> I am afraid, but this does not give constant amortized time.

sendEmail :: ProperlyThoughtOut Idea -> IO ()

Clearly my brain lacks a type checker.

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Red-Blue Stack

[Jamie Brandon]

Try writing

data RBStack = RBS [RBSItem] [RBSItem]

where the first list are all the same colour and the start of the
second list is a different colour. The rest should follow naturally
and you will get amortised O(1) push and pop (you occasionally have to
juggle the lists).

By the way, for this kind of question you'll get help much faster if
you ask on #haskell.

Jamie

On Thu, Sep 25, 2008 at 5:11 AM, Matthew Eastman <[EMAIL PROTECTED]> wrote:
> Hey guys,
>
> This is probably more of a question about functional programming than it is
> about Haskell, but hopefully you can help me out. I'm new to thinking about
> things in a functional way so I'm not sure what the best way to do some
> things are.
>
> I'm in a data structures course right now, and the assignments for the
> course are done in Java. I figured it'd be fun to try and implement them in
> Haskell as well.
>
> The part of the assignment I'm working on is to implement a RedBlueStack, a
> stack where you can push items in as either Red or Blue. You can pop Red and
> Blue items individually, but the stack has to keep track of the overall
> order of items.
>
> i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red, Red, Blue]
>
> All push and pop operations on the stack have to be done in O(1) time.
>
> It was easy to do in Java since you can just keep track of everything with a
> few pointers, but it took a while to get the Haskell version working. Maybe
> I'm just not used to the functional way of doing things.
>
> I originally had this:
>
> data RBSItem a = Red a | Blue a
>
> data RedBlueStack a = RBS {
>red :: [RBSItem a],
>blue:: [RBSItem a],
>overall :: [RBSItem a]
> }
>
> But there was no way to keep popping in O(1) time because I would have to
> walk through the overall list when removing items.
>
> I eventually came up with:
>
> data ShowColour = PlusRed | MinusRed | PlusBlue | MinusBlue
>
> data RedBlueStack a = RBS {
>red   :: [a],
>blue  :: [a],
>order :: [ShowColour]
> }
>
> popRed :: RedBlueStack a -> RedBlueStack a
> popRed (RBS (r:rs) b o) = RBS rs b (MinusRed : o)
> popRed rbs@(RBS [] _ _) = rbs
>
> -- As an aside here, would it be better to put "popRed = id" for the
> catch-all in popRed instead of what I have?
> -- I don't know proper Haskell coding style yet.
>
> remUseless :: [ShowColour] -> [ShowColour]
> remUseless order@(x:xs)
>| x == MinusRed  = remShowColour PlusRed xs
>| x == MinusBlue = remShowColour PlusBlue xs
>| otherwise = order
>where
>remShowColour r (c:cs)
>| c == r= cs
>| otherwise = c : remShowColour r cs
>remShowColour _ [] = error "Incorrect Stack Order"
>
> So instead of walking through the overall list, I just have to add a
> MinusRed or MinusBlue to the order list. This makes the pop and push
> functions operate in O(1) time, but it seems a bit excessive, because
> whenever the overall order of the stack is needed (e.g. printing the stack)
> I need to clean up the order list.
>
> I was just wondering whether this is the best way to implement something
> like this, keeping track of changes made instead of making the changes. If
> anyone has any ideas for other ways of implementing this I'd love to see
> them.
>
> I didn't take into account that Haskell is lazy. Will that have any effect
> on the running time? Probably not for a simple program like this, but for
> larger ones and more complex data structures and algorithms, I'm guessing it
> would?
>
> Thanks,
> Matt
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Architecturally flawed

[Jamie Brandon]

I have a similar piece of code at http://code.haskell.org/gmap/serial/
which is fairly well tested. It currently only outputs lists of words
but its based on Data.Binary so it should be fairly easy to get
bytestrings out it (bytestrings worked up till 2-3 weeks ago, I just
havent bothered to keep the byestring part up to date).I dont yet know
how fast it is but I will be tweaking it over the next month or so.

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Planet haskell

[Jamie Brandon]

I was hoping to have my summer of code blog added to planet haskell
but [EMAIL PROTECTED] no longer seems to exist. Hopefully
the owner is subscribed to this list?

Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe