April 2006 - Haskell-Cafe

Re: [Haskell-cafe] 1G strings in Haskell
by dons＠cse.unsw.edu.au 20 Apr '06

20 Apr '06

dagit: > On 4/19/06, Donald Bruce Stewart <dons(a)cse.unsw.edu.au> wrote: > > Question: > > Can I manipulate 1G strings in Haskell? > > > > > > Failed due to memory exhaustion. > > Almost made it though, just need a tad more ram than I had. > > > > filter ! > > unlines ! > > unwords ! > > reverse ! -- copy > > cons ! -- copy > > snoc ! -- involves a copy > > ++ ! -- can't concat two 1G strings on this box > > I would say given the nature of the experiment that you want to feed > these functions with values that lead to 1 GB results. At least, that > makes sense in the case of ++, but maybe not the others. Yes, good point. Previous experiments with 500M strings indicated that these all worked fine: Size of test data: 531416k Fine: filter 7.264 unwords 1.715 reverse 1.980 cons 0.976 snoc 0.689 ++ 2.845 Still wouldn't work at 0.5G unlines ! concat ! > Did the machine have any available swap? If so, why was it not used? Swap was used, 1G more, but ulimits kicked in a few times (and I'm not an admin on the box). This was a bit frustrating, but the 0.5G results show what is possible. > The strings had to be in memory all at once to not skew the benchmark > by including I/O time? The strings were all in memory, yes, with some deepSeq tricks. -- Don

1 0

1G strings in Haskell
by dons＠cse.unsw.edu.au 20 Apr '06

20 Apr '06

Question: Can I manipulate 1G strings in Haskell? Short answer: Yes! Mostly. Doing some stress testing of FPS, here are some results for 1G strings. 3.2Ghz box, 2G physical mem. Size of input string: 1G N.B. 2G of physical ram is not enough when trying to benchmark functions that copy 1G strings around :) Function Time in seconds All O(1) functions: length O index 0 head 0 tail 0 last 0 init 0 O(n) , but answer found early on: compare 0 any 0 all 0 elem 0 elemIndex 0 O(n) mostly: maximum 3.855 minimum 4.666 filterChar 8.084 elemIndicies 11.504 lines 12.247 find 14.046 tails 27.328 inits 33.620 words 100.963 map toUpper 143.871 Failed due to memory exhaustion. Almost made it though, just need a tad more ram than I had. filter ! unlines ! unwords ! reverse ! -- copy cons ! -- copy snoc ! -- involves a copy ++ ! -- can't concat two 1G strings on this box sort ? taking too long, but space was ok. [Char] functions are much more costly. pack ! -- constructing 1G [Char] is not ok. unpack ! Lesssons, you can play with 1G strings in Haskell. Having more than 2G ram is useful though. Replacing higher order functions with hard coded first order equivalents can help. -- Don

1 0

Re: [Haskell-cafe] Advice needed on best way to simulate an STL vector
by Cale Gibbard 19 Apr '06

19 Apr '06

I should perhaps point out that in the development GHC (iirc), there is a library called Data.Sequence which uses 2-3 finger trees to get rather nice efficient sequences. Operations on both ends (appending or dropping) are constant time, while operations in the middle tend to be on the order of the logarithm of the distance to the closer of the two ends. For instance, concatenation and splitting at a point both have complexity proportional to the logarithm of the smaller of the two parts involved. - Cale On 19/04/06, Brian Hulley <brianh(a)metamilk.com> wrote: > Thanks. I might try this if I don't have any luck with finger trees (from > Udo's post), or if they seem too heavy for the simple thing I'm planning to > use them for (implementing the text buffer for an edit control which needs a > mutable array of lines where each line contains a mutable array of character > info). I don't need non-Int indices so your data type for Vector would be > fine. > > Best regards, Brian. > >

2 1

RE: [Haskell-cafe] Proposal for restructuring Number classes
by Andrew U. Frank 19 Apr '06

19 Apr '06

i am most grateful to henning and dylan for their effort in restructuring the number classes. there seems to be agreement, that the current classes are not optimal. the decision what goes in a class depends enormously on what axioms one is assuming for an operation symbol. should * always be commutative or is its use for non-commutative types acceptable? i will now make an effort to use the proposed classes by dylan and hennig and adapt my code to it and then come back and report how it suited my needs. thank you for the help! andrew frank

2 1

Re: Proposal for restructuring Number classes
by Serge D. Mechveliani 17 Apr '06

17 Apr '06

On Sat, Apr 08, 2006 at 02:39:39PM +0200, Andrew U. Frank wrote: > there has been discussions on and off indicating problems with the structure > of the number classes in the prelude. i have found a discussion paper by > mechveliani but i have not found a concrete proposal on the haskell' list of > tickets. > i hope i can advance the process by making a concrete proposal for > which i attach Haskell code and a pdf giving the rational. if i have not > found other contributions, i am sorry. > > i try a conservative structure, which is more conservative than the > structure we have used here for several years (or mechveliani's proposal). > It suggests classes for units (Zeros, Ones) and CommGroup (for +, -), > OrdGroup (for abs and difference), CommRing (for *, sqr), EuclideanRing (for > gdc, lcm, quot, rem, div...) and Field (for /). I think the proposed > structure could be a foundation for mathematically strict approaches (like > mechveliani's) but still be acceptable to 'ordinary users'. > > i put this proposal for discussion here and hope for suggestions how it can > be improved before i put it to haskell'! > > andrew frank > For a long time, there exist the following documents and programs * BAL library (implemented, downloadible) -- Basic Algebra Library for Haskell, which was a proposal for a new "Num"-like library. * A paper "Haskell and computer algebra" which describes the idea of BAL. * A paper "What should be an universal functional language", which describes, what are the problems of Haskell as related to algebra. These three items can be downloaded from www.botik.ru/~mechvel by clicking at BAL, and at the papers you choose. The main problem with the language can be illustrated by the following example. The domain Matrix(n, m) of matrices n by m depends on the ordinary values. These n, m can be computed in some cycle at run time. But in Haskell, we need to model a _domain_ as a _type_, with several _instances_ for this type. And these latter cannot evolve at run time. For example the domain Matrix(3, m) must have MultiplicativeSemigroup instance -- if m == 3, and must not have such instance otherwise. And m may change at run-time. This is the reason for why BAL looks so complicated -- and why the proposal has been rejected. (By the way, both these papers have been rejected by the conference referrees of the Haskell community and FP community). I think that without dependent types for a Haskell-like language, it is impossible to propose any adequate and in the same time plainly looking algebraic class system. ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2

Justification for Ord inheriting from Eq?
by Brian Hulley 17 Apr '06

17 Apr '06

Hi - I've been wondering for a long time if there is a reason why Ord should inherit from Eq and not vice versa, or whether in fact there is any justification for making either Ord or Eq inherit from the other one. For example, Ord and Eq could alternatively be defined as: class Ord a where (<), (<=), (>=), (>) : a -> a -> Bool x <= y = not (y < x) x >= y = not (x < y) x > y = y < x class Ord a => Eq a where (==), (/=) :: a -> a -> Bool x /= y = x < y || y < x x == y = not (x /= y) Part of the reason for my question is that it seems to me that the lesson from object oriented programming is that inheritance is usually a bad idea, since very few things (perhaps nothing?) have a single natural taxonomy (witness the efforts to reorganise the numeric hierarchy that have been alluded to on this list). In languages such as C++ the only "good" use of inheritance seems to be when you have an abstract base class representing an interface and multiple concrete derived classes (as immediate children of it) representing the implementations, but in Haskell, this is the class/instance distinction, so I can't see a strong reason why Haskell classes should be allowed to inherit from other classes. Except perhaps Monad, MonadIO, MonadPlus etc... Any thoughts? Thanks, Brian.

14 22

Re: coherence when overlapping?
by oleg＠pobox.com 16 Apr '06

16 Apr '06

> But I am still confused by the exact definition of coherence in the case of > overlapping. Does the standard coherence theorem apply? If yes, how? > If no, is there a theorem? Yes, the is, by Martin Sulzmann et al, the Theory of overloading (the journal version) http://www.comp.nus.edu.sg/~sulzmann/ms_bib.html#overloading-journal A simple intuition is this: instance selection may produce more than one candidate instance. Having inferred a polymorphic type with constraints, the compiler checks to see of some of the constraints can be reduced. If an instance selection produces no candidate instances, the typechecking failure is reported. If there is exactly one candidate instance, it is selected and the constraint is removed because it is resolved. An instance selection may produce more then one candidate instance. Those candidate instances may be incomparable: for example, given the constraint "C a" and instances "C Int" and "C Bool", both instances are candidates. If such is the case, the resolution of that constraint is deferred and it `floats out', to be incorporated into the type of the parent expression, etc. In the presence of overlapping instances, the multiple candidate instances may be comparable, e.g. "C a" and "C Int". The compiler then checks to see if the target type is at least as specific as the most specific of those candidate instances. If so, the constraint is reduced; otherwise, it is deferred. Eventually enough type information is available to reduce all constraints (or else it is a type error).

3 4

Re: [Haskell] ANNOUNCE: An index-aware linear algebra library in Haskell
by Alberto Ruiz 16 Apr '06

16 Apr '06

On Friday 14 April 2006 17:02, Frederik Eaton wrote: > An index-aware linear algebra library in Haskell Excellent work! Is it possible to create a vector or matrix whose size is not known at compile time? > - Due to the need to specify index types at some point, input of > vectors is difficult. I have provided two functions in Fu.Vector.Base > which should cover most of the cases: > > listVec :: Vector v e => [e] -> (forall n . (ReflectNum n) => v (L n) -> w) > -> w > listMat :: Vector v e => [[e]] -> > (forall n m . (ReflectNum n, ReflectNum m) => v (L m, L n) -> w) -> w > > However, these aren't useful in interactive situations. So I have also > provided some template-haskell routines > > http://ofb.net/~frederik/futility/src/Vector/Template.hs > > which can be used to instantiate vectors directly. For example: (In examples.hs): >-- matrix with elements of type Double >v6 = trans $(dAM [[1,2,3,4]]) > >v7 = $(dAM [[1,0,0],[0,1,0],[0,0,1],[1,1,1]]) -- Alberto

2 3

Re: [Haskell-cafe] Code Review: Sudoku solver
by Michael Hanus 16 Apr '06

16 Apr '06

Jared Updike wrote: > On 3/22/06, David F. Place <d(a)vidplace.com> wrote: > ... > > It solves > > sudoku puzzles. (What pleasure do people get by doing these in their > > heads?!?) > > > > They are probably asking the same question: why take hours to write a > program to do it when with my mad sudoku solving skills I can solve it > in X seconds? My roommate is like this. I would say because they have chosen the wrong language for this problem :-) Solving Sudoku is a typical finite domain constraint problem. Thus, a language with constraint solving facilities like Curry (a combination of Haskell and constraint logic programming) is much better suited. Actually, I wrote a Sudoku solver in Curry and the actual code for the solver is 10 lines of code which is compact and well readable (if you are familiar with Haskell), see http://www.informatik.uni-kiel.de/~curry/examples/CLP/sudoku.curry Regards, Michael

11 35

web servers
by Tim Newsham 15 Apr '06

15 Apr '06

Hi Everyone, I'm new to the list, been on irc a bit. I'm still learning haskell. Wanted to say Hi before getting in to things... I'm interested in real-world programs in haskell, especially ones where security and formal methods are important. I'm looking at web servers right now. I found a copy of Simon Marlow's HWS on haskell.org's cvs server. I know there's a newer plugin version, but I cant find a working link to the actual code. I've been able to get the code to compile after a while, but it still has some warnings of deprecated features which I havent been able to get rid of (if anyone's interested in helping out, let me know). Anyway, I configured it an ran it and it works, although I have noticed two security flaws in it which need fixing. Is it possible there is a newer version with these flaws fixed? Besides HWS, what other web servers exist? Does anyone actually use a haskell based web server in practice? Which web server is considered the most mature? stable? fastest? I'm trying to decided if I should sink some time into HWS or if I should use another server. Tim Newsham http://www.lava.net/~newsham/

6 7