- Haskell-Cafe - Haskell.org

Problem
by Michael Sterling 17 Oct '04

17 Oct '04

I am trying to create a function in Haskell which accepts a list, and goes through each element in the list, appending the element to a separate string, and then I want to print out that string (currently, it takes a list of values, and prints out the same list of values).

1 0

Subsequence
by Peter Stranney 17 Oct '04

17 Oct '04

I am stuck on an exercise in a haskell book (the craft of functional programming) chapter 7 exercise 7.18 I have to write a function to check does one list occur as a subsequence of another, i am having real difficulty trying to do this. I have a method which will tell me if one character occurs in the list but it won't work for a list of characters. the function should look like isSubsequence :: [chars] -> [chars] -> boolean any help on this, even a polymorphic type function would be greatly appreciated Thank you Peter Stranney Peter Stranney --------------------------------- Do you Yahoo!? vote.yahoo.com - Register online to vote today!

2 1

OO idioms redux
by John Goerzen 17 Oct '04

17 Oct '04

OK, recently I posed a question about rethinking some OO idioms, and that spawned some useful discussion. I now have a followup question. One of the best features of OO programming is that of inheritance. It can be used to slightly alter the behavior of objects without requiring modification to existing code or breaking compatibility with existing APIs. As an example, say I have a ConfigParser class. This class can read in configuration files, provides various get/set methods to access them, and can write them back out. Now say I would like to make this a little more powerful. Maybe I want to support the use of environment variables in my config file, so if there's a reference to $FOO in the file, it will be replaced by the contents of $FOO in the environment. In OO, I would make a new EnvConfigParser class. I'd override the read() method. My new read() would probably start by calling the parent's read() method, to get parsing for free. Then it could iterate over the data, doing its environment variable substitution. Now, in Haskell, we obviously have no objects like this. We do have something that provides some of the same benefits -- typeclasses. However, from what I can determine, they don't support algorithm inheritance like objects do in an OOP. Specifically, it seems impossible to have two instances of a single typeclass that work on the same type, while having one share most of the code with the other. I'm wondering if there is a Haskell design pattern that I'm missing that would provid ethe kind of benefits that one gets from inheritance in the OO world. -- John -- John Goerzen Author, Foundations of Python Network Programming http://www.amazon.com/exec/obidos/tg/detail/-/1590593715

7 14

functional programming school
by Matthew Roberts 15 Oct '04

15 Oct '04

I am looking for a functional programming summer school in the next 12 months. I realise there was one August this year, does anyone know of any others coming up? Matt

3 2

automatic vectorisation
by Matthew Roberts 15 Oct '04

15 Oct '04

Hi all, I am working on automatic vectorisation of functional code (by compiler). If there is anyone else interested in this, I would love to hear from you. If there is anyone else already working on this, or planning to in the near future, I would hate to be replicating someone else's work - much better to work together!!! This work is in pursuit of a PhD and so I am taking on a meaty project. Matt

1 0

Re: wc again (Lists and type classes)
by MR K P SCHUPKE 15 Oct '04

15 Oct '04

Of course when I say it's neater - I mean if the List class were defined in the libraries, so only the short definition of 'wc' given at the beginning of my last post would be required! Keean.

1 0

wc again (Lists and type classes)
by MR K P SCHUPKE 15 Oct '04

15 Oct '04

Have been playing with the idea of a list class like the one I posted earlier... but now a bit streamlined. I have implemented wc using this class and a nice buffer list. The result is something 4 times slower than the current language-shootout code, but is rather neater. The restriction on getting the full speed of the current code is the requirement to freeze the IOUArray to get it out of the IO monad. This could be solved with an "IOList" type but this would not be compatible with the types for a 'normal' list. Here's the code for wc: -------------------------------------------------------------- main :: IO () main = do l <- hGetIList 4096 stdin print $ wc l ' ' 0 0 0 wc :: List l Word8 => l Word8 -> Char -> Int -> Int -> Int -> (Int,Int,Int) wc l p i j k | p `seq` i `seq` j `seq` k `seq` False = undefined | not $ Main.null l, h <- (toEnum . fromEnum . Main.head) l, t <- Main.tail l = case isSpace h of False -> wc t h (i + 1) (j + if isSpace p then 1 else 0) k _ -> wc t h (i + 1) j (k + if h == '\n' then 1 else 0) | otherwise = (i,j,k) --------------------------------------------------------------- And here's the definition of the list class and instances (one is provided for a normal list for reference) -------------------------------------------------------------- {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Main where import Char import GHC.IOBase import System.IO import Data.Word import Data.Array.IO import Data.Array.Unboxed data IList a i e = ICons i i (a i e) (IList a i e) | INil class List l e where nil :: l e null :: l e -> Bool head :: l e -> e tail :: l e -> l e (+:) :: e -> l e -> l e class List (l a i) e => ListPlus l a i e where (++:) :: a i e -> l a i e -> l a i e part :: a i e -> i -> l a i e -> l a i e infixr 9 +: infixr 9 ++: instance List [] e where nil = [] null (_:_) = False null _ = True head (a:_) = a tail (_:l) = l a +: l = a:l instance (IArray a e,Ix i,Num i) => List (IList a i) e where nil = INil null INil = True null _ = False head (ICons i _ a _) = a!i head _ = error "head: empty list" tail (ICons i j a l) | i < j = ICons (i+1) j a l | otherwise = l tail _ = error "tail: empty list" a +: l = ICons 0 0 (array (0,0) [(0,a)]) l instance (IArray a e,Ix i,Num i) => ListPlus IList a i e where a ++: l | e >= s = ICons s e a l | otherwise = l where ~(s,e) = bounds a part a i l | e >= i = ICons s i a l | otherwise = l where ~(s,e) = bounds a hGetIList :: Int -> Handle -> IO (IList UArray Int Word8) hGetIList bufSize h = do mt <- newArray_ (0,bufSize-1) ioLoop mt where ioLoop mt = unsafeInterleaveIO $ do sz <- hGetArray h mt bufSize hd <- freeze mt case sz of 0 -> return nil n | n < bufSize -> do return (part hd (n-1) nil) | otherwise -> do tl <- ioLoop mt return (hd ++: tl) -------------------------------------------------------------------------- Keean.

1 0

Re: [Haskell-cafe] Haskell's overlooked object system: was OO idioms redux
by MR K P SCHUPKE 15 Oct '04

15 Oct '04

>Although I still miss a simple primitive language construct to do >'extensible record', If you look at the OOHaskell, and HList papers, you will see the neatest way of defining an HList based extensible record is: record = label1 .=. value1 .*. label2 .=. value2 .*. label3 .=. value3 .*. emptyRecord A record is built by using the record-product operator (.*.) on a label-value pair and a record... emptyRecord is obviously provided so you can start with 'nothing'. All the class definitions to make this possible are hidden in the HList library... The only other thing required is to declare your labels... Keean.

1 0

Re: [Haskell-cafe] Haskell's overlooked object system: was OO idioms redux
by MR K P SCHUPKE 14 Oct '04

14 Oct '04

>'extensible record' proposal. HList is extensible records implemented in Haskell + multi-parameter types and functional dependancies. In other words you can already do all the recordy stuff in Haskell... HList is simply a collection library using these techniques. >Haskell 98 does not have row-polymorphism, does it? See above... Basically using HLists as the core of an object representation you can do all the forms of inheritance and virtual functions that OCaml has (and more?) Again OOHaskell is simply a library (in Haskell) to make this easy. There are no new language extensions required and we can do anything in the OCaml tutorial. This is interesting because we can reduce all the mechanisms of OO programming to type-classes, and from there to System F. Keean,

1 0

Re: [Haskell-cafe] Re: [Haskell] lazy constructors
by Serge D. Mechveliani 14 Oct '04

14 Oct '04

I thank Jeremy Gibbons, Ben Rudiak-Gould, and other people, for their helpful explanations. On Wed, Oct 13, 2004 at 02:34:55PM +0100, Ben Rudiak-Gould wrote: > Serge D. Mechveliani wrote: > > > As the types are resolved before the computation, as the above > > program shows, how can addToSPair expect anything besides a string > > pair? Why tilda is not a default? > > Haskell pairs are "lifted", meaning that they also include an extra > value (bottom) which doesn't match (x,y). Not everyone is convinced that > this is a good idea, but it's the way things are at present. > > > The only doubt may be the matching of (xs, ys) against > > bottom :: (String, String) Is not this natural to have a result as > > (bottom :: String, bottom :: String) -- = xs = ys and > > compute further? > > Possibly in this case, yes. But not in general, since there might be > other data constructors also. > > > What will occur if all the Haskell programmers set `~' before each > > data constructor in each pattern in their existing programs? > > Things won't work as you'd expect. For example, if you defined > > null :: [a] -> Bool > null list = > case list of > ~(x:xs) -> False > ~[] -> True > I am sorry. Of course, I meant the functions in which it was set initially only a single pattern. People often write such. > > As the types are recognized before the computation, the programs will > > remain safe and will become considerably faster. For example, the > > above program of g1 becomes a billion times faster. I wonder. > > Actually using irrefutable patterns tends to make a program slower, not > faster, because it makes the program less strict. > Probably, unneeded strictness bites more seriousely than unneeded laziness. What I fear of is the following hidden slow down. Suppose that such a function (as the above addToPair) updates a value of type ([a], [b]) in a loop. And consider a client function let p = form_list_pair_via_addToPair ... ... h = g p p ... in if (take 3 $ fst p) == "abc" then ... else ... The value of p is used in several places, the whole program looks natural. The programmer relies on that (take 3 $ fst p) computes `lazily'. In fact, I like to rely on the `laziness' and think that it makes the programs more clear. Otherwise, one could program, say, in ML. Now, if one does not guess to set tilda in addToPair, the whole program becomes slower somewhat in (length xs)/3 times! Here xs is a list accumulated in the first component of the form_list_pair_via_addToPair result. If length xs = 900, then the slow down in 300 times. Is there any systematic approach allowing to avoid a performance adventure like this? May the compiler help, may it issue a warning? And maybe, there are other sources of the slow downs due to unneeded strictness. Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Re: [Haskell-cafe] Haskell's overlooked object system: was OO idioms redux
by oleg＠pobox.com 14 Oct '04

14 Oct '04

Just to clarify: the intent of the OOHaskell paper is to show that Haskell, *as it is*, already has an OO system that is at least as powerful as that found in C++, Java, Eiffel, OCaml. Actually, it is strictly more powerful than the OO systems of C++, Java, Eiffel. In OCaml, the Object system is an extension, with its own extensive syntax and _quite non-trivial_ type system. We show that we can do the same in Haskell without any extensions, and roughly in the same syntax (that is, modulo the usual syntactic differences between non-OO OCaml and Haskell). It is not our intent to pass judgment as to whether an implementation inheritance or multiple inheritance are good or bad. We merely want to show: - if you want implementation inheritance, here's how you do it in Haskell, roughly in the same syntax as in other OO languages, and with the same semantics as in other OO languages - if you want interface inheritance, here's how you do it in Haskell, roughly in the same syntax and with the same semantics - if you want multiple inheritance, here's .... - if you want open recursion and selective closing of open recursion, here's ... Ditto for virtual and private methods, objects in ST monad, overriding, polymorphic classes and methods. I'd really like to hear if there are OO buzzwords we have missed... Again, we do *not* propose to extend Haskell in any way. We do not need to introduce special subclassing and subtyping judgments into the type system, deal with co- and contra-variance and the implicit weirdly-typed 'this', etc. The existing typechecker does all this for us. Our aim is to clarify the relation between object systems and typeclasses, to clarify various, often quite baroque, OO type systems, and provide a lightweight library and a set of guidelines to let one play with an OO of their preference using existing Haskell implementations. You can use as many or as few OO features in Haskell as you wish.

1 0

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults
by J.Garrett.Morris＠Dartmouth.EDU 13 Oct '04

13 Oct '04

--- Ketil Malde wrote: Or, what if String were one? Could we have painless read/show with arrays of Char, as well as lists, for instance? --- end of quote --- I think with a decent set of type classes for collections, better handling of strings would come for free. If any list function could be made implementation independent, then strings could still be treated as lists of chars, but the underlying implementation could be completely different (arrays, PackedStrings, etc.) /gXm

1 0

RE: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults
by Simon Marlow 13 Oct '04

13 Oct '04

On 07 October 2004 18:23, Ketil Malde wrote: > Couldn't readFile et al. provide the standard interface, but use > hGetBuf tricks (e.g. from your 'wc' entry) behind the curtains? readFile does do buffering behind the scenes, that's not the problem. The problem is doing the computation on a [Char] instead of a raw buffer of bytes. There are various known techniques that could be used to speed up GHC's implementation of lists, none of which we've ever tried. This might be a good area for experimentation, if anyone's looking for something to do in GHC. Cheers, Simon

10 13

RE: [Haskell] is $ a no-op?
by Graham Klyne 13 Oct '04

13 Oct '04

[Switched to haskell-cafe] At 13:24 13/10/04 -0400, Jacques Carette wrote: > > > -- It's kind of like an converse map. > > > > I have attempted, unsuccessfully, to write flist above in a point-free > > manner. Is it possible? > > > Of course it is, but why? > > flist = flip (map . flip ($)) > >Some functions are simpler point-free, others are simpler with points. I >was curious about this one (I like the pointwise version better). > >Also, the statement "It's kind of like a converse map" becomes quite clear >from the point-free way to write it, while still not so obvious in the >pointwise version. The point-free form can be deduced thus, I think: flist fs a = map ($ a) fs (flip flist) a fs = map ($ a) fs -- swap flist args (flip flist) a = map ($ a) -- redundant arg (flip flist) a = map ((flip ($)) a) -- expand section (flip flist) a = (map . (flip ($))) a -- definition of . (flip flist) = map . (flip ($)) -- redundant arg flist = flip (map . (flip ($))) -- move flip to RHS #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Re: [Haskell] lazy constructors
by Serge D. Mechveliani 13 Oct '04

13 Oct '04

On Wed, Oct 13, 2004 at 10:06:44AM +0200, Sander Evers wrote: > > >Question 2 > >---------- > >How to arrange the above `lazy' output? > > > > > Your function addToSPair > > addToSPair :: Char -> (String, String) -> (String, String) > addToSPair c (xs, ys ) = (c:xs, ys ) > > does a strict pattern match on the pair constructor. It needs to know > that its second argument is a pair before it produces anything of its > result. If you use a lazy pattern match > > addToSPair :: Char -> (String, String) -> (String, String) > addToSPair c ~(xs, ys ) = (c:xs, ys ) > > instead, it doesn't need to evaluate this argument immediately. !! This is great, thank you. This improves a lot. I never recalled of the tilda for several years. Excuse me for the stupidity, but I have a next naive question. As the types are resolved before the computation, as the above program shows, how can addToSPair expect anything besides a string pair? Why tilda is not a default? --------------------------------------------- repeating: bottomStr :: String bottomStr = let xs = xs in xs bottomSPair :: (String, String) bottomSPair = let p = p in p longToReach = 10^8 :: Int f1, f2, g1, g2 :: Char f1 = head ('a' : (if last [1 .. longToReach] > 0 then "b" else "c")) f2 = head ('a' : bottomStr) addToSPair :: Char -> (String, String) -> (String, String) addToSPair c (xs, ys ) = (c:xs, ys ) g1 = head $ fst $ addToSPair 'a' (if last [1 .. longToReach] > 0 then ("b", "") else ("c", "")) g2 = head $ fst $ addToSPair 'a' bottomSPair ----------------------------------------------------------------- The only doubt may be the matching of (xs, ys) against bottom :: (String, String) Is not this natural to have a result as (bottom :: String, bottom :: String) -- = xs = ys and compute further? What will occur if all the Haskell programmers set `~' before each data constructor in each pattern in their existing programs? As the types are recognized before the computation, the programs will remain safe and will become considerably faster. For example, the above program of g1 becomes a billion times faster. I wonder. Copy, please, the answer to mechvel(a)botik.ru ----------------- Serge Mechveliani mechvel(a)botik.ru

2 1

Re: [Haskell-cafe] Re: [Haskell] lazy constructors
by MR K P SCHUPKE 13 Oct '04

13 Oct '04

>addToSPair :: Char -> (String, String) -> (String, String) What about: addToSPair :: Char -> String -> String -> (String,String) so that the pattern match is: addToSPair c xs ys = (c:xs,ys) This is irrefutable? Keean.

1 0

Re: [Haskell] lazy constructors
by Serge D. Mechveliani 13 Oct '04

13 Oct '04

On Wed, Oct 13, 2004 at 09:23:43AM +0100, MR K P SCHUPKE wrote: > You can only return a list of pair's lazily, not > a pair of lists. If the two strings are independant, then > generate each in a separate function, and pair off the > results lazily. No, I have several labeled fields in a record, which are very dependent. As people teach, the costruct of ~(..,..) helps for the Pair. Maybe, the labeled record can also be handled ... ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Re: [Haskell-cafe] RE: [Haskell] lazy constructors
by MR K P SCHUPKE 13 Oct '04

13 Oct '04

>addToSPair c ~(xs, ys ) =3D (c:xs, ys ) I thought pattern bindings had an implicit "~"? Keean.

1 0

RE: [Haskell] lazy constructors
by Simon Peyton-Jones 13 Oct '04

13 Oct '04

[I think this thread would be more appropriate on haskell-café, so I'm redirecting it] | addToSPair :: Char -> (String, String) -> (String, String) | addToSPair c (xs, ys ) = (c:xs, ys ) | | --------------------------------------------------------------- | | g1 is similar to f1, g2 similar to f2. | | f1 and f2 are evaluated immediately to 'a'; | | g1 evaluates to 'a' after a long computation; | g2 evaluates to Fail: <<loop>> | | As g2 is similar to f2, should it have a value 'a' ? | In | head $ fst $ addToSPair 'a' bottomSPair Try using lazy pattern matching, thus addToSPair :: Char -> (String, String) -> (String, String) addToSPair c ~(xs, ys ) = (c:xs, ys ) The only change is the "~" in the defn of addToSPair. Now g2 will have value 'a'. Simon

1 0

strictness and the simple continued fraction
by William Lee Irwin III 13 Oct '04

13 Oct '04

So, I discovered that simple continued fractions are supposed to be spiffy lazy lists and thought I'd bang out some continued fraction code. But then I discovered ContFrac.hs and couldn't really better it. Of course, I went about trying to actually do things relying on their laziness, and discovered they weren't as lazy as I hoped they'd be. Simple uses of approximations at the ghci command line such as: instance Ord ContFrac where (ContFrac (x:xs)) `compare` (ContFrac (y:ys)) = case x `compare` y of LT -> LT GT -> GT EQ -> (ContFrac ys) `compare` (ContFrac xs) (ContFrac []) `compare` cf = case cf of ContFrac (x:_) -> 0 `compare` x ContFrac [] -> EQ cf `compare` (ContFrac []) = case cf of ContFrac (x:_) -> x `compare` 0 ContFrac [] -> EQ x = expCF (1/2) where expCF x | x < 0 = recip . expCF $ negate x | x == 0 = 1 | x == 1 = let ContFrac es = ecf in ContFrac (take 100 es) | otherwise = case x of ContFrac [y] -> (expCF 1)^y ContFrac (y:ys) -> if y /= 0 then ((expCF 1)^y) *(expCF (ContFrac (0:ys))) else (1+x+x^2/2+x^3/6+x^4/24+x^5/120) ContFrac [] -> expCF 0 where the instance was added to ContFrac.hs seems to fail to terminate, where manually reducing things a bit appears to restore termination. So, what hit me? -- wli

3 5

Tutorial about low-level I/O in Haskell
by Peter Simons 12 Oct '04

12 Oct '04

Hi, while polishing a small library of mine, I ended up writing a tutorial about the use of hGetBufNonBlocking and the related Foreign.* functions you need to do fast, block-oriented I/O in Haskell. There is something to be said for literate programming. Using recent topics for inspiration, the text describes the implementation of a fast word-counting program. :-) Here is the URL: http://cryp.to/blockio/docs/tutorial.html Peter

2 2

Strict evaluation not working?
by Christian Hofer 12 Oct '04

12 Oct '04

Hi, having found a bit of time to play with Haskell, I am trying to figure out how to enforce strict evaluation. I wrote the following program: main = let x = zipWith (+) [5..] [6..] in putStrLn $ show $ x `seq` head x I expected this program not to terminate - because of the seq-Operator, but it happily returns 11 in ghc as well as in ghci. What do I make wrong? Chris

3 3

Re: Language extension idea (was Re: [Haskell-cafe] Re: OCaml list sees...)
by J.Garrett.Morris＠Dartmouth.EDU 12 Oct '04

12 Oct '04

--- Tom Pledger wrote: It could get more convenient, though, if we have data-constructors-as-class-members and move the familiar list constructors into the List class. (The following might need to be built into the compiler, because of the special [] syntax.) --- end of quote --- Changing the subject very slightly, this brings up two questions: 1) Wouldn't implementing the Views proposal allow this? and, 2) Why haven't views been implemented (and why are they a "never" in the HaskellTwo discussion in HaWiki)? /gXm

3 2

Re: [Haskell-cafe] List implementation.
by MR K P SCHUPKE 12 Oct '04

12 Oct '04

>class List l where > head :: IArray UArray a => l a -> Maybe a > tail :: IArray UArray a => l a -> Maybe (l a) changed my mind about this... you cannot do: tail $ tail $ tail x so added a 'null' test instead.

1 0

Re: [Haskell-cafe] List implementation.
by MR K P SCHUPKE 12 Oct '04

12 Oct '04

Hows this: ... tail (Many i a l) | i < (e-s) = (Many (i+1) a l) | otherwise = l where (s,e) = bounds a ... a ++: l | e >= s = Many s a l | otherwise = l where (s,e) = bounds a A futher though is that with constructors you can do: f (a:as) = f [] = As you cannot use the constructors to access the list elements here, maybe the following would be more useful: class List l where head :: IArray UArray a => l a -> Maybe a tail :: IArray UArray a => l a -> Maybe (l a) then you can write: f x | Just h <- head x = ... | otherwise = ... Keean.

1 0

List implementation.
by MR K P SCHUPKE 12 Oct '04

12 Oct '04

With reference to the discussion a couple of days ago about list implementations, here is some code showing the idea I was talking about... Its a list that you can write either single elements or blocks (UArrays) to, but it always reads like a list of elements, so blocks can be read in, but you can recurse over individual elements. There is obviously some overhead with this in-haskell implementation, but if this were the default list implementation in the RTS, you could use the encoding trick I mentioned before to get practically no overhead for its use. -------------------------------------------------------------- {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module List where import Data.Array.Unboxed data AList a = One !a (AList a) | Many !Int !(UArray Int a) (AList a) | Nil class List l where head :: IArray UArray a => l a -> a tail :: IArray UArray a => l a -> l a (+:) :: IArray UArray a => a -> l a -> l a (++:) :: IArray UArray a => (UArray Int a) -> l a -> l a infixr 9 +: infixr 9 ++: instance List AList where head (One a _) = a head (Many i a _) = a!i tail (One _ l) = l tail (Many i a l) | i < la = (Many (i+1) a l) | otherwise = l where (_,la) = bounds a a +: l = One a l a ++: l = Many 0 a l --------------------------------------------------------------- Keean.

2 1

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootout results
by MR K P SCHUPKE 12 Oct '04

12 Oct '04

One to add to your list, string edit distance - as its hard, and useful. Keean.

1 0

RE: [Haskell-cafe] strictness and the simple continued fraction
by Simon Peyton-Jones 12 Oct '04

12 Oct '04

If you are interested in arbitrary precision arithmetic using continued fractions, you may want to check out the work of David Lester. And Peter Potts et al. Just type "exact real arithmetic" into Google. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | William Lee Irwin III | Sent: 12 October 2004 04:53 | To: Scott Turner | Cc: haskell-cafe(a)haskell.org | Subject: Re: [Haskell-cafe] strictness and the simple continued fraction | | On Mon, Oct 11, 2004 at 09:53:16PM -0400, Scott Turner wrote: | > I tried using continued fractions in a "spiffy lazy list" implementation a | > while ago. Never got them working as well as expected. | > Evenutally I realized that calculating with lazy lists is not as | > smooth as you might expect. | > For example, the square root of 2 has a simple representation | > as a lazy continued fraction, but if you multiply the square root of 2 by | > itself, your result lazy list will never get anywhere. The calculation will | > keep trying to determine whether or not the result is less than 2, this being | > necessary to find the first number in the representation. But every finite | > prefix of the square root of 2 leaves uncertainty both below and above, so | > the determination will never be made. | > Your problems may have some other basis, but I hope this helps. | | I hit that one, too. That's nasty enough it may be best to give up on | the infinite case, at least. I can't think of a way to salvage all this. | | | -- wli | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootout results
by MR K P SCHUPKE 12 Oct '04

12 Oct '04

I though clean was always strict, and that was the major difference between clean and haskell (that and the fact clean is a proprietry language) Keean.

13 15

Being Compatible
by John Goerzen 11 Oct '04

11 Oct '04

Hi, I have appreciated some of the comments here about what exactly is standardized. My next question is how to work at the greatest number of places. I am working on a library of Haskell-related utilities. There is some code in there that works with binary I/O, and some code that works with rawSystem(), etc. Some of these are not supported on Hugs, nhc98, or ghc5 to varying degrees. My initial thought was to use the cpp-style ifdefs I've seen elsewhere to mask those unsupported features on those particular systems. But Hugs at least doesn't support that, and I've found it extremely difficult to find a list of predefined macros for the other systems anyway. What is the suggested way to work around these problems?

3 2

Re: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
by MR K P SCHUPKE 11 Oct '04

11 Oct '04

>No, you still have to copy "aaaa" so you can change the tail pointer Do you? If "aaaa" is treated as a single buffer contents (IE implemented as a UArray Int Char for example) then as our 'new' list implementation# can have cells which are single elements of buffers of elements, we simply 'cons' the buffer onto the beginning of the list (IE the next pointer is not in the constants string but the cell containing it) Keean.

1 0

empty Array?
by Abraham Egnor 11 Oct '04

11 Oct '04

As a project mostly motivated by personal curiosity, I've been implementing a Sequence class: class Sequence s where front :: s a -> (a, s a) back :: s a -> (s a, a) null :: s a -> Bool empty :: s a prepend :: a -> s a -> s a append :: s a -> a -> s a concat :: s a -> s a -> s a The intent is to make it almost as easy to use, via pattern guards, as pattern matching on lists: map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x:map f xs smap :: Sequence s => (a -> b) -> s a -> s b smap f s | null s = empty | (a, s') <- front s = prepend (f a) $ smap f s' It is, of course, trivial to implement this for lists. I've run into a snag, however, when trying to implement this for Arrays (as in Data.Array) - I can't seem to find a way to represent an empty array, which makes implementing 'empty' and 'null' impossible. Suggestions? Abe

2 1

RE: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
by MR K P SCHUPKE 11 Oct '04

11 Oct '04

> - take this further and have list cells with 2 (or more) unboxed > characters, or even a full buffer. This sounds like the best idea to me... with each list cell being a full buffer you could effectively write nieve [Char] code and have it implemented in about as fast a way as possible... A little improvement on this would be to do a bit of read ahead, so that the filesystem latency can be hidden. (ie one thread reads the next buffer, whilst the application thread processes the previous buffer)... This would also benefit string processing... Imagine: test = "aaaa" ++ "bbbb" This could be implented as two list cells, one for each string, anf the cost of the "++" becomes the same as the cost of ":" test = 'a' : "bbbb" could be implemented in exactly the same way (a cell of size one and a cell of size 4) In this way with the cell size dependant on the source, lists generated by prepending characters would remain exactly as they are. The only slight complexity would be allowing 'next' pointers to point halfway through a cell, so that if you start with "dddd" remove the first character and prepend 'c' the original list "dddd" could still be in scope. Keean.

4 3

NewbieQ: colon prefix for operators, e.g., Ratio ?
by Brian Beckman 11 Oct '04

11 Oct '04

Apologies if this is the wrong mailing list in which to pester folks with Newbie Questions, but I couldn't find my answer after half an hour of scouring the Haskell Report, the Haskell Wiki, the School of Expression book and a couple of tutorials. The frustrating thing is that I know I saw the answer in ONE of those sources and it didn't stick at the time: what does it mean when an operator is prefixed by a colon? For instance, in the Ratio module, the meaning of x % y is clear, but x :% y appears in multiple places and I'm confused.

2 1

Re: Language extension idea (was Re: [Haskell-cafe] Re: OCaml list sees...)
by J.Garrett.Morris＠Dartmouth.EDU 10 Oct '04

10 Oct '04

--- Malcolm Wallace wrote: As an example, instead of the following list-only code, f :: List a -> ... f [] = ... f (h:t) = ... you could write this more general version, which assumes only some class Sequence with operations null, head, tail, etc. f :: Sequence s => s a -> ... f list | null list = ... | h <- head list, t <- tail list = ... --- end of quote --- I guess that's about half way there. I (and, I think, the original poster) was thinking more along the lines of generalizing the existing interface and considering lazy lists to be one implementation. It seems like the "list" syntax is general enough to apply to any ordered collection. Further, that would only require minimal changes in large amounts of existing code that relies on, for example, Strings being [Char]s were Strings changed to a more efficient representation. /gXm

1 0

Language extension idea (was Re: [Haskell-cafe] Re: OCaml list sees...)
by oleg＠pobox.com 09 Oct '04

09 Oct '04

Tom Pledger wrote: > Something along these lines: > > class List l a | l -> a where > nil :: l > cons :: a -> l -> l > > But that's not of much use, because there isn't a class method to > recover the elements of a List. We could add more methods (corresponding > to null, head, and tail) Actually we merely need to add a deconstructor. Also, we can leave the type of elements fully polymorphic. Something like this: > class List l where > nil :: l a > cons :: a -> l a -> l a > decon :: l a > -> w -- on empty > -> (a -> l a -> w) > -> w > > instance List [] where > nil = [] > cons = (:) > decon [] on_nil on_cons = on_nil > decon (h:t) on_nil on_cons = on_cons h t we can then write truly generic list-processing functions: > rev:: List l => l a -> l a > rev l = rev' l nil > where > rev' l acc = decon l acc (\h t -> rev' t (cons h acc)) not in a terribly convenient way though. *Foo> rev "abc" "cba"

2 1

Re: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
by MR K P SCHUPKE 09 Oct '04

09 Oct '04

>In general only specific *code* can be compiled more efficiently. I disagree - If GHC optimised as much as is _possible_ the code would be as fast and use as little memory as hand coded 'C' >It can't be transparent. A different type for semi-packed strings, Again I disagree... I dont see why you cannot change the "implementation" of lists without changing the "interface"... Good old lists will behave like good old lists - just the implementation would try and take advantage of blocking of the data wherever possible. Perhaps a pragma to change the implementation of lists would ne be a sensible way of selecting the implementation. If a clever way of encoding the node-size (for large cells) is used, then it would be no slower than normal list code... One way of doing this would be to only change the format of cells where the next link is null (IE the end of the list)... In this case normal cells would be encoded _exactly_ as they are at the moment (so no slowdown or increase in memory usage) - to encode a large cell, the next pointer is null, and then an extra data structure determines if this really is the end of the list, or if infact it is a large cell (so we need an item count, and a _real_ next cell link, plus the data block) Keean.

3 2

Re: IPv6?
by Dominic Steinitz 09 Oct '04

09 Oct '04

> ------------------------------ > > Message: 2 > Date: Fri, 8 Oct 2004 14:10:35 +0000 (UTC) > From: John Goerzen <jgoerzen(a)complete.org> > Subject: [Haskell-cafe] Re: IPv6? > To: haskell-cafe(a)haskell.org > Message-ID: <slrncmd7ur.6dr.jgoerzen(a)christoph.complete.org> > > On 2004-10-08, Simon Marlow <simonmar(a)microsoft.com> wrote: > >>On 07 October 2004 21:43, John Goerzen wrote: >> >> >>>Network.Socket in GHC6 seems to be restricted to IPv4, despite the >>>prsence of AF_INET6. How do I support IPv6 in Haskell? >> >>You write some code to handle IPv6 and send it to us for inclusion in >>Network.Socket ;-) > > > OK, fair enough, let's go down that path for a moment :-) > > I probably could figure out how to do that based on the existing IPv4 > code. Some small parts of IPv6 support are already there. > > However, I'd have two questions: > > 1. Wouldn't there need to be some sort of discussion first to ensure > that all the compiler/interpreter implementors do it the same way? > > 2. I don't know anything about the autotools stuff save that it does not > get along very well with me. If I submit a patch that assumes that IPv6 > support is available, would somebody be able to add the appropriate > tests and ifdefs around it to ensure that it really is? > > -- John > John, Maybe I'm badly informed but there is hardly any usage of IPv6. What's driving you to want to use it? Dominic.

1 0

ANN: MissingH
by John Goerzen 09 Oct '04

09 Oct '04

Hi, Well here is why I've been asking all these questions in here. Comments welcome. Thank you for all your help. Download or read docs at: gopher://quux.org/1/devel/missingh http://quux.org/devel/missingh Here are excerpts from the README file: ------------------------- Major Features ------------------------- * Powerful Logging Framework for Haskell This framework provides a system of hierarchical loggers and modular handlers permitting fine-grained logging with a great deal of control and yet a simple and fast interface. It's based on log4j for Java and logging for Python. Also included is a native-Haskell Syslog client. * IO utilities make it easier to work with line-based text files and binary files * List utilities including association list tools, list splitting, truncation, and delimiter joining * String utilities including removal of leading or trailing whitespace, joining, splitting, and truncation The entire library has no prerequisites save the Haskell standard library and is designed to install without complexity on a variety of systems. It could also easily be embedded within your own source trees so that users need not have it installed beforehand.

1 0

The State Monad
by John Goerzen 09 Oct '04

09 Oct '04

This thing is giving me fits. I need a global variable of sorts for an implementation of Syslog. (Yes, I really do.) It seems the right way to do that is the state monad. But I can't figure out how to do two simple things: * Read what is in there without modifying it * Modify it appropriately I looked at the examples in Control.State.Monad. We see: tick :: State Int Int tick = do n <- get put (n+1) return n Add one to the given number using the state monad: plusOne :: Int -> Int plusOne n = execState tick n Which looks nice enough, but completely useless. tick seems to be a very complex way to say ((+) 1) in this example. Oddly enough, I get a type error if I try this: tick :: Int -> State Int Int tick newval = do put newval return newval Or this: tick :: State Int Int tick = do n <- get return n That is even more incomprehensible to me -- why would removing a line before the return cause a type error?

4 4

OCaml list sees abysmal Language Shootout results
by Keith Wansbrough 08 Oct '04

08 Oct '04

I just saw this on the OCaml list (in a posting by "Rafael 'Dido' Sevilla" <dido(a)imperium.ph> in the "Observations on OCaml vs. Haskell" thread). I can't believe that a simple "wc" implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? --KW 8-) http://caml.inria.fr/archives/200409/msg00485.html > > 2. Haskell strings are lists of characters > > > > It's annoying that strings aren't normally processed this way in OCaml, > > and even more annoying that (^) or (::) cannot be used in pattern > > matching over strings. I like Haskell's approach. The list > > concatenation operator is the same as the string concatenation operator > > in Haskell. > > > > This is something of an efficiency/elegance tradeoff. Making strings > act like lists means potentially boxing *every character in the string*. > In other words, it's potentially a very expensive way of doing business. > Paul Graham was mulling over this kind of tradeoff in his design of Arc, > as I recall. Another language that does this type of thing is Erlang, > and both languages seem to be significantly slower than OCaml in string > handling, at least as far as this site goes: > > http://shootout.alioth.debian.org/ > > For the word count benchmark OCaml scores 0.1850 seconds, while GHC is a > dismal last place at 105.2110 seconds! Even the bytecode ocaml is an > order of magnitude faster. The word frequency benchmark also shows this > kind of poor string handling performance for Haskell, with OCaml scoring > 0.5669 seconds, while GHC scores a truly dismal 6.4540, more than an > order of magnitude slower, and even the bytecode ocaml is faster at > 4.2644 seconds. > > All in all, it would appear that Haskell's approach has been expensive > in terms of performance, if the benchmarks are to be taken at face > value. Such are the tradeoffs language designers have to make.

18 43

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults
by MR K P SCHUPKE 08 Oct '04

08 Oct '04

Doubly linked lists do not work very well in functional languages.# when you have a list [1,2,3] and you prepend a value [9,1,2,3] the language relies on the fact that the list tail [1,2,3] is not chainged by this operation. This means the list can be "prepended-in-place". With a doubly linked list the [1] cell would be changes (the 'left' pointer is changed from null to point to the [9] cell)... The result of this is that with a doubly linked list the _whole_ list must be copied when prepending a single value. In other words in a functional language, a doubly linked list will make ':' as hard as '++' and not the other way round! Keean.

1 0

RE: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
by Simon Marlow 08 Oct '04

08 Oct '04

On 08 October 2004 13:36, Robert Dockins wrote: > BTW can you give some references to these known techniques? Hmm, well here's some folklorish ideas. I'm sure there are references for most of these, but I don't know them off hand. - Have another list constructor that has 2 (or more) elements. Prelude funnctions can take advantage of this, but the constructor can magically transform itself into ordinary cons cells when it is examined by an ordinary pattern match. - take this further and have list cells with 2 (or more) unboxed characters, or even a full buffer. - use space-saving techniques for storing list cells: eg. remove the tail pointer when cells appear next to each other in the heap, or have a memory page just for list cells and omit the info pointers. Or just improve cache behaviour by trying to store list cells adjacent in the heap. Cheers, Simon

1 0

A Typing Dilemma
by John Goerzen 08 Oct '04

08 Oct '04

Thanks so much for all the help many of you have provided. I have one (heh) more question: I have this code: defaultHandler :: LogHandler b => IO (a -> IORef b) defaultHandler = do h <- (streamHandler stdout WARNING) r <- newIORef h return (\x -> r) The idea is to create a new IORef to something in the LogHandler class and return a function that returns it. The thing returned by that call to streamHandler is in the LogHandler class. Specifically, its declaration looks like this: instance LogHandler (GenericHandler a) where ... and streamHandler returns a "GenericHandler Handle" object. Now, when compiling that defaultHandler code, the compiler complains: Cannot unify the type-signature variable `b' with the type `MissingH.Logging.Handler.Simple.GenericHandler Handle' Expected type: IORef b Inferred type: IORef (MissingH.Logging.Handler.Simple.GenericHandler Handle) In a lambda abstraction: \ x -> r In the first argument of `return', namely `(\ x -> r)' I'm stumped. Can anyone shed some light on that for me? Thanks, -- John

2 1

RE: [Haskell-cafe] Being Compatible
by Simon Peyton-Jones 08 Oct '04

08 Oct '04

John Yes, I think your best route is cpp-ery, horrible though it is. I suggest you use ghc6.2.1 (or 6.2.2 when it comes out, which will be Monday-ish), rather than some ghc5.x version. Otherwise you risk investing work in making a library incompatible with the current story. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of John | Goerzen | Sent: 07 October 2004 15:35 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Being Compatible | | Hi, | | I have appreciated some of the comments here about what exactly is | standardized. My next question is how to work at the greatest number of | places. | | I am working on a library of Haskell-related utilities. There is some | code in there that works with binary I/O, and some code that works with | rawSystem(), etc. | | Some of these are not supported on Hugs, nhc98, or ghc5 to varying | degrees. | | My initial thought was to use the cpp-style ifdefs I've seen elsewhere | to mask those unsupported features on those particular systems. But | Hugs at least doesn't support that, and I've found it extremely | difficult to find a list of predefined macros for the other systems | anyway. | | What is the suggested way to work around these problems? | | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

RE: [Haskell-cafe] Re: IPv6?
by Simon Marlow 08 Oct '04

08 Oct '04

On 08 October 2004 15:11, John Goerzen wrote: > I probably could figure out how to do that based on the existing IPv4 > code. Some small parts of IPv6 support are already there. > > However, I'd have two questions: > > 1. Wouldn't there need to be some sort of discussion first to ensure > that all the compiler/interpreter implementors do it the same way? We all share libraries, so anything you do to Network.Socket will appear in all the compilers, provided it is portable enough. If there are issues about how the interface to IPv6 should be exposed to the programmer, then the best place to discuss it is libraries(a)haskell.org. I suspect that it'll be pretty straightforward, though - Network.Socket is a low level interface that just tries to re-expose the OS primitives as a Haskell library. > 2. I don't know anything about the autotools stuff save that it does > not get along very well with me. If I submit a patch that assumes > that IPv6 support is available, would somebody be able to add the > appropriate tests and ifdefs around it to ensure that it really is? Probably... we have one or two autoconf-compliant hackers amongst the GHC regulars. Cheers, Simon

1 0

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootout results
by Peter Achten 08 Oct '04

08 Oct '04

At 03:32 PM 10/8/2004, Marcin Kowalczyk wrote: >Andrew Butterfield <Andrew.Butterfield(a)cs.tcd.ie> writes: > > >>I though clean was always strict, and that was the major difference > >>between clean and haskell (that and the fact clean is a proprietry > >>language) > > > > No - Clean is pure and lazy like Haskell, > >But it uses explicit strictness annotations a lot, and provides strict >and/or unboxed versions of various fundamental types (e.g. tuples), >with some implicit coercions. It is of course not the language that uses strictness annotations. Clean programs without strictness annotations are perfectly lazy. Clean has a powerful strictness analysis that includes only safe strictness to function arguments. Programmers *can* include strictness annotations, exactly for the reasons that were mentioned in this thread, namely to influence the evaluation strategy in such a way that heap consumption and/or run time decrease. In addition, this can be done light-weight because annotations are added only to function argument types and data types, instead of modifying the code by inserting strict evaluator functions. Regards, Peter Achten N.B. My new email address is : P.Achten(a)cs.ru.nl. The University of Nijmegen has changed its name to Radboud University Nijmegen

1 0

RE: [Haskell-cafe] IPv6?
by Simon Marlow 08 Oct '04

08 Oct '04

On 07 October 2004 21:43, John Goerzen wrote: > Network.Socket in GHC6 seems to be restricted to IPv4, despite the > prsence of AF_INET6. How do I support IPv6 in Haskell? You write some code to handle IPv6 and send it to us for inclusion in Network.Socket ;-) Cheers, Simon

2 1

Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults
by MR K P SCHUPKE 08 Oct '04

08 Oct '04

>lists doubly-linked and circular. Erm, this just increases overhead, and file access is linear anyway. Singly linked is good enough. What would make a difference is if each 'node' in the listwas allowed to be larger that '1' item. For example reading a file with 4k buffers, would work much better if the list were represented by 4k chunks in a liked list. Keean.

1 0

RE: [Haskell-cafe] more shootout madness -- hashes in GHC
by Simon Marlow 08 Oct '04

08 Oct '04

On 07 October 2004 20:53, Robert wrote: > I've been playing around with the "Hashes, Part II" code from the > shootout. I wanted to try to implement this test using Data.HashTable > instead of Data.FiniteMap to see if that would buy us anything. In > fact, the HashTable implementation is consistantly faster than > FiniteMap, but not by a lot (thus making the transition to the IO > monad not worthwhile IMO). The interesting thing, however, is that > at a certain number of iterations (106 in my case), the Hashtable code > segfaults. GDB shows that it is blowing the top off the program stack > and dying when it tries to write to kernel space. (can't write to > 0xbfffffff). Thanks, that's a good bug to catch just before the 6.2.2 release. There is a performance bug in the 6.2.2 HashTable implementation which we already found, but I forgot to merge into the 6.2 branch. The performance bug caused the table to overflow, leading to the segfault (not checking for overflow is another bug). Upshot: this will be fixed in 6.2.2. Furthermore, performance will be better. Cheers, Simon

1 0