March 2006 - Haskell-Cafe

Eval of a syntax tree for reduction
by Steve Downey 28 Mar '06

28 Mar '06

I'm working through Pierce's Types and Programming Languages on my own. I'm attempting to write the typecheckers in Haskell, instead of ML. However, when it comes to his eval function, I'm a little stuck. The original is let rec eval t = try let t' = eval1 t in eval t' with NoRuleApplies -> t Where eval1 is a single step evaluation of the abstract syntax tree, and NoRuleApplies is an exception that's raised if there are no rules that can reduce the expression. Now, there's a footnote that it isn't good style in ML. It seems even less natural in Haskell, at least to me, but I still don't know the language that well. The natural equivalent to what Pierce has in ML is something along the lines of data ArithExpr = TmTrue | TmFalse | TmIfExpr ArithExpr ArithExpr ArithExpr | TmZero | TmSucc ArithExpr | TmPred ArithExpr | TmIsZero ArithExpr deriving (Show, Eq) eval1 :: ArithExpr -> ArithExpr eval1 (TmIfExpr TmTrue t _) = t eval1 (TmIfExpr TmFalse _ t) = t eval1 (TmIfExpr t1 t2 t3) = let t1' = eval1 t1 in TmIfExpr t1' t2 t3 -- and so on But, how to terminate the recursion in the full eval? I'm considering changing eval1 to be ArithExpr->Maybe ArithExpr If the expression is reducible, then I return Just t, and if it's not reducible, then Nothing It makes eval1 a bit more complicated, and not as straightforward translation from the type system being described, though. e.g reducing If looks more like eval1 (TmIfExpr t1 t2 t3) = let t1' = eval1 t1 in case t1' of { Just t1'' -> Just $ TmIfExpr t1'' t2 t3 ; Nothing -> Nothing } and eval then looks like eval t = let t' = eval1 t in case t' of { Just t'' -> eval t'' ; Nothing -> t' } I'm looking for some suggestions on the direction to proceed.

3 2

Bit streams programs in Haskell
by Per Gustafsson 27 Mar '06

27 Mar '06

Haskell gurus, We have made a proposal to extend the Erlang `binary' data type from being a sequence of bytes (a byte stream) to being a sequence of bits (a bitstream) with the ability to do pattern matching at the bit level. This proposal has now been fully implemented all these at the level of the BEAM virtual machine and in the HiPE compiler. Most probably, they will be part of the next major Erlang/OTP open source release. (We write "most probably" because we do not really control what Ericsson desides to release as part of its open source system.) We wanted to evaluate the performance of our implementation and the succintness of our syntax, particularly against other `similar' languages. For this reason, we wrote five reasonably representative benchmarks, showing the things that one could employ bit stream pattern matching and bit-level comprehensions for. The benchmarks (drop3, five11, huffman, uudecode, and uuendode) have all been written in Erlang, O'Caml and Haskell. For some of them, C and Java versions exist. They can be found in the following homepage: http://bitbenches.infogami.com/ As you will see there, the Haskell numbers are significantly slower than those of Erlang and O'Caml. We are wondering why this is so. For each language, we have spent a considerable effort in writing the benchmarks in -- at least what we feel -- is the most natural and efficient way one can write them. The only constraint we impose is that for functional languages, data structures without any explicit mutation have to be used in the part of the program for which measurements are taken. Our experience in writing efficient (and beautiful) Haskell programs is close to (if not below) zero. Also, perhaps our mind might be suffering from severe case of strictness and might be completely unable to `think lazily'. So, we request your help in noticing obvious NO-NOs and stupid mistakes that we might have made. We even welcome completely different Haskell programs provided they adhere to the constraint mentioned above -- no mutation. Best regards, Kostis Sagonas and Per Gustafsson

5 6

Re: Equirecursive types?
by John Hughes 27 Mar '06

27 Mar '06

>From: Ross Paterson <ross(a)soi.city.ac.uk> > >On Sun, Mar 26, 2006 at 01:22:17PM -0500, Jim Apple wrote: > > >>According to Pierce's book, O'Caml has an optional equirecursive type >>extension that turns off the occurs check. Is there any particular >>reason Haskell doesn't have that available? >> >> > >It's certainly feasible, though turning off the occurs check doesn't >do it: you need to use the unification algorithm for regular trees (see >e.g. section 6.7 of the revised Dragon Book). You also need to decide >what to do about > > type T = T > >I think the arguments against it are: > * many common errors will lead to perfectly legal types. > * it adds convenience, but not expressive power. > * it only works for regular types, where the arguments of uses of the > type constructor on the rhs are the same as (or a permutation of) > the arguments on the lhs, so this is out: > > type T a = Either a (T (a,a)) > > > Indeed, error messages in common cases would be worsened significantly, because as Ross says, common errors (such as forgetting a parameter in a recursive call) would lead to legal definitions that cause a type error when applied. Partly for this reason, OCaml permits recursion only in object types, if I remember rightly, where it's most useful. In other cases the occurs check is still used. John

1 0

(!!) operator usage
by Neil Rutland 27 Mar '06

27 Mar '06

Hi there, I hope i have sent this in the right format - i gather i may have been rude by sending it incorrectly - if this is still wrong give me a shout. Anyway today i am enquiring about how to use the !! operator - i have looked at Zvons Haskell refeernce and it says that it takes a list( like newLine below) and an Integer for the location of the item you wish to return. Basically in this example i would like to return the value 4 type Bob = [(Int, Int)] newLine :: Bob newLine = [(1,4)] i have tried to use the follwing but it returns the error below it. newLine !! 0 - (so that should give it the newLine list and try and return the 1st element of the list) the error reads thus ERROR file:.\VicotriaLine.txt:107 - Type error in final generator *** Term : newLine !! 0 *** Type : (Int,Int) *** Does not match : IO a Could someone please try and tell me what thats all about because i can't see what i am doing wrong based on the examples i have found from the website i detailed about. Cheers everyone Neil

3 3

Building Monads from Monads
by Daniel McAllansmith 26 Mar '06

26 Mar '06

Hi, I've got a few (9) random questions, mainly about monads and building monads from existing monads, partly trying to confirm conclusions I've come to through experimentation. Any, and all, attempts to enlighten me will be much appreciated. Thanks Daniel First, terminology. In StateT s (ReaderT r IO) () Q. 1) StateT is referred to as the outermost monad, and IO as the innermost monad, correct? Using a monadic function, eg MonadReader.ask, in a monadic expression will access the outermost monad of the appropriate class. Q. 2) Does this work for all monad classes in all expressions? How does Control.Monad.Trans.lift work? It seems that a single application of lift will find the next outermost monad of the appropriate class, but if you want to dig deeper into the nest you need to apply lift according to the monads actual depth in the nest. Q. 3) Why the different behaviour? Q. 4) Is it possible to give a type to the lifted function so that the monad of the correct class _and_ type is used? E.g. dig into a String Reader rather than an Int Reader. Defining an instance of MonadTrans for a monad instance seems universally useful. Q. 5) Are there obvious situations where it's not useful or possible? Carrying out IO in a nested monadic expression requires liftIO. Apart from having to type an extra 7-9 characters it seems good to use liftIO even in plain IO monad expressions so they can become nested expressions with no trouble later on. Q. 6) Is it safe to always use liftIO, even in plain IO monad? Q. 7) If it's safe to do, why aren't functions in the IO monad just typed in the MonadIO class instead? It looks to me like types with class constraints are better than types specifying nests of monad instances. So g :: (MonadReader String m, MonadState Int m, Monad m) => m () is better than g :: StateT Int (Reader String) () because you can change the instance of the monadic class at will. Also you can change the nesting order of the monads, though maybe that's not useful in practice. The disadvantage seems to be that you can't use lift to access nested monads. Q. 8) Is it possible to get access to nested monads when using class constraint types? In the following code, the test2 function is not valid because there is no instance for (MonadCounter (ReaderT [Char] (StateT Word IO))), which is a fair enough complaint. Q. 9) What allows ReaderT and StateT to be nested in arbitrary order but not ReaderT and CounterT? Especially given CounterT is actually a StateT. class (Monad m) => MonadCounter m where increment :: m Word decrement :: Word -> m () type Counter = State Word instance MonadCounter Counter where increment = increment_ decrement = decrement_ runCounter :: Counter a -> a runCounter c = evalState c 0 type CounterT m = StateT Word m instance (Monad m) => MonadCounter (CounterT m) where increment = increment_ decrement = decrement_ runCounterT :: (Monad m) => CounterT m a -> m a runCounterT c = evalStateT c 0 increment_ :: (MonadState Word m) => m Word increment_ = do w <- get put (w + 5) return w decrement_ :: (MonadState Word m) => Word -> m () decrement_ w = do curW <- get if w > curW then put 0 else put (curW - w) return () test1 :: IO () test1 = runReaderT (runCounterT bar) "blah" --test2 :: IO () --test2 = runCounterT (runReaderT bar "blah") bar :: (MonadReader String m, MonadCounter m, MonadIO m) => m () bar = do w <- increment s <- ask liftIO $ putStrLn $ (show w) ++ s return ()

2 4

Equirecursive types?
by Jim Apple 26 Mar '06

26 Mar '06

According to Pierce's book, O'Caml has an optional equirecursive type extension that turns off the occurs check. Is there any particular reason Haskell doesn't have that available? Here's what got me thinking about it: http://lambda-the-ultimate.org/node/1360#comment-15656 Jim

2 1

The simple programming language,
by pinturicchio 26 Mar '06

26 Mar '06

if somebody can help me wid this i wil b realy thankful Finally, we come to the program. The simple programming language, which includes loops, conditionals and sequential composition will be expressed a datatype in Haskell. data Prg = Skip | PrintS String | PrintE Exp | Declare Variable | Variable := Exp | Prg :> Prg | IfThenElse Exp (Prg, Prg) | While Exp Prg The program Skip does nothing. The program PrintS ‘prints’ the given string to the output. Similarly, PrintE prints the value of the given expression to the output. Declare declares a variable, assigning its initial value to 0. The := operator performs variable assignment. The :> operator is sequential composition, while IfThenElse and While are conditional and while-loops respectively. The condition in both cases resolves to true if the value of the expression is not zero. A factorial program can be programmed in this small language as follows: counter = "counter" result = "result" factorial n = Declare counter :> Declare result :> result := Val 1 :> counter := Val n :> While (Var counter) ( result := (Var result) :*: (Var counter) :> counter := (Var counter) :-: (Val 1) ) :> PrintS ("Factorial of "++show n++" is:") :> PrintE (Var result) (a) The simulate function takes a Store and a program, and returns an updated store and list of output strings: simulate :: Store -> Prg -> (Store, [String]) Using pattern matching, define simulate for Skip, PrintS and variable declarations. (b) Add the cases for PrintE and variable assignment. (c) Sequential composition can be defined by simulating the two instructions in sequence. Complete the following case: simulate store (p1 :> p2) = let (store’, outs1) = simulate store p1 (store’’,outs2) = simulate store’ p2 in ... (d) Define simulate for conditionals. (e) We can ‘cheat’ by simulating while-loops in terms of conditionals and sequential compositi simulate store (While condition program) = simulate store (IfThenElse condition ( program :> While condition program , Skip ) ) Using this definition, test your program with the factorial program. -- View this message in context: http://www.nabble.com/The-simple-programming-language%2C-t1344638.html#a359… Sent from the Haskell - Haskell-Cafe forum at Nabble.com.

2 1

A Haskell Tutorial
by Jonathan Tang 26 Mar '06

26 Mar '06

Hi all, I've written a Haskell tutorial that walks the reader through the implementation of a Scheme interpreter: http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html Instead of focusing on small examples at the Haskell REPL, it tries to show the reader how to construct a real program with Haskell. It introduces monads and IO early, and also includes error checking, state, file I/O, and all the other "hard stuff" that's frequently omitted from beginner tutorials. Am looking for feedback on two main axes: 1.) Experienced Haskell users: is this more-or-less idiomatic Haskell? Did I miss any library or language features that could make the programmer's job easier? It was my first substantial Haskell program, so I worry that I may have missed some common ways of doing things. 2.) Novices: is it clear and easy to understand? I had a tough time figuring out how to do anything practical in Haskell, because most tutorials omit IO, gloss over monads, and don't pay any attention to state or error-checking. Does this rectify those shortcomings? Comments/critiques are appreciated. Regards, Jonathan

1 0

pls fast help me with this simple question
by iliali16 26 Mar '06

26 Mar '06

type Data = Integer type Variable = String type Store = [(Variable, Data)] Store = [("",0)] emptystore :: Store emptystore = [("",0)] getVal :: Store -> Variable -> Data thats my code i just have to continue and get the value of a variable from the store but i don't know how the task is : Define a function getVal, which takes a Store and a variable name, and returns its value. You may assume that the variable is defined in the Store. getVal :: Store -> Variable -> Data (c) Define a function setVar, which takes a Store, a variable name and a value, and returns an updated Store with the variable value updated. setVal :: Store -> (Variable, Data) -> Store -- View this message in context: http://www.nabble.com/pls-fast-help-me-with-this-simple-question-t1345292.h… Sent from the Haskell - Haskell-Cafe forum at Nabble.com.

2 1

Question about "Arrows and Computation" by Paterson
by Reilly Hayes 24 Mar '06

24 Mar '06

I've been taking a close look at the paper "Arrows and Computation" by Ross Paterson. It's not relevant to my question, but I'm doing this because I think that Arrows may be a useful abstraction for a problem I have (I need to both construct a computational pipeline AND perform a computation over the pipeline itself). The paper is published as Chapter 10 in "The fun of Programming" and is also available here: http://www.soi.city.ac.uk/~ross/papers/fop.html My question originates with the statement at the bottom of page 205 (the 5th page of the paper) regarding the behavior of the function 'first': " ... while 'first' routes the state through f:". My problem is that this statement appears to be erroneous. My reading of the code would indicate that 'first' does not do this at all. The state portion of the Arrow remains unaltered. Nor does it even seem desirable for 'first' to have an impact on the state portion of the Arrow, as I would think that this would preclude using 'first' and 'second' to lift binary operators into the Arrow. So what is it that am I missing? The relevant code is as follows. Paterson used Greek letters where I have used Latin. I represented his product operator with the letter x, requiring surrounding backquotes. If there are other changes to his code I am unaware of them and they are an error on my part. class Arrow a where pure :: (b -> c) -> a b c (>>>) :: a b c -> a c d -> a b d first :: a b c -> a (b,d) (c,d) x :: (a -> a') -> (b -> b') -> (a,b) -> (a',b') (f `x` g) ~(a,b) = (f a, g b) assoc :: ((a,b),c) -> (a,(b,c)) assoc ~(~(a,b),c) = (a,(b,c)) unassoc :: (a,(b,c)) -> ((a,b),c) unassoc ~(a,~(b,c)) = ((a,b),c) newtype State s i o = ST ((s,i) -> (s,o)) instance Arrow (State s) where pure f = ST (id `x` f) (ST f) >>> (ST g) = ST (g . f) first (ST f) = ST (assoc . (f `x` id) . unassoc) -Reilly Hayes

2 2