October 2004 - Haskell-Cafe

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