- Haskell-Cafe - Haskell.org

Using existential types
by Graham Klyne 08 Oct '03

08 Oct '03

I've been trying to use existential types [*] in my code. [*] cf. Glasgow Haskell Compiler (GHC) user guide, section 7.3.12 My experiments have thrown up a couple of questions: 1. forall x introduces x as existential when it appears immediately preceding a datatype constructor declaration, e.g. at -1- below. In position -2-, it appears to signal a universal quantifier. Is this a correct reading of the situation? 2. I have been trying to use existential types to allow an auxiliary type to appear in the implementation of a datatype, and have ended up using one datatype to "wrap" another. Is there a cleaner way? The code below has been adapted from my development code to provide a stand-alone example of the kind of thing I'm trying to do. It runs OK under Hugs. #g -- -- spike-existential.hs -- -- experimenting with existential types -- -- Questions: -- -- 1. forall x introduces x as existential when it appears immediately -- preceding a datatype constructor declaration, e.g. at -1- below. -- In position -2-, it appears to be a universal quantifier. -- ? -- -- 2. Is there cleaner way to hide the datatype vt in the declaration -- of DatatypeVal below, on the basis that I don't really want it to -- be visible outside the inference rules that are specific to this -- datatype, referenced by typeRules If I apply the existential at -- position -1-, an error is reported by Hugs: -- "cannot use selectors with existentially typed components". -- -- The approach I have adopted is to define two datatypes, -- DatatypeVal which is parameterized by expression type and value -- type, and Datatype which wraps a DatatypeVal with the value -- type being an existential. I've yet to work out implementation -- details for the stuff that uses the value type, but I anticipate -- using a constructor function that takes the DatatypeMap value -- as an argument. -- data Expr = Expr String -- Dummy expression type for spike deriving Eq data Ruleset ex = Ruleset ex String -- Dummy ruleset type for spike deriving Eq -- Type Datatype wraps DatatypeVal with an existential, thus -- hiding the value type. Also define access methods for those -- components that don't reference the value type. data Datatype ex = forall vt . Datatype (DatatypeVal ex vt) typeName (Datatype dtv) = tvalName dtv typeSuper (Datatype dtv) = tvalSuper dtv typeRules (Datatype dtv) = tvalRules dtv -- Type DatatypeVal uses a value type (vt) in its implementation. -- See tvalMap; the intent is that an implemenatation of tvalRules, -- and other code may make use of this component. data DatatypeVal ex vt = DatatypeVal {-1- data DatatypeVal ex = forall vt . Datatype -1-} { tvalName :: String , tvalSuper :: [Datatype ex] -- ^ List of datatypes that are each a supertype -- of the current datatype. The value space -- of the current datatype is a subset of the -- value space of each of these datatypes. -- NOTE: these supertypes may be implemented -- using a different value type; e.g. a -- supertype of xsd:integer is xsd:decimal , tvalMap :: {-2- forall vt. -2-} DatatypeMap vt -- ^ Lexical to value mapping, where 'vt' is -- a datatype used within a Haskell program -- to represent and manipulate values in -- the datatype's value space , tvalRules :: Ruleset ex -- ^ A set of named expressions and rules -- that are valid in in any theory that -- recognizes the current datatype. } data DatatypeMap vt = DatatypeMap { mapL2V :: String -> Maybe vt -- ^ Function to map lexical string to -- datatype value. This effectively -- defines the lexical space of the -- datatype to be all strings for which -- yield a value other than Nothing. , mapV2L :: vt -> Maybe String -- ^ Function to map a value to its canonical -- lexical form, if it has such. } datatypevalXsdInteger :: DatatypeVal Expr Integer datatypevalXsdInteger = DatatypeVal { tvalName = "http://www.w3.org/2001/XMLSchema#integer" , tvalSuper = [datatypeXsdInteger] , tvalMap = mapXsdInteger , tvalRules = rulesetXsdInteger } datatypeXsdInteger :: Datatype Expr datatypeXsdInteger = Datatype datatypevalXsdInteger -- |mapXsdInteger contains functions that perform lexical-to-value -- and value-to-canonical-lexical mappings for xsd:integer values -- mapXsdInteger :: DatatypeMap Integer mapXsdInteger = DatatypeMap { -- mapL2V :: String -> Maybe Integer mapL2V = \ s -> case [ x | (x,t) <- reads s, ("","") <- lex t ] of [] -> Nothing is -> Just $ head is -- mapV2L :: Integer -> Maybe String , mapV2L = Just . show } rulesetXsdInteger = Ruleset (Expr "expr") "rules" -- Checkout test1 = typeName datatypeXsdInteger == "http://www.w3.org/2001/XMLSchema#integer" test2 = typeName (head $ typeSuper datatypeXsdInteger) == typeName datatypeXsdInteger test3 = typeRules datatypeXsdInteger == rulesetXsdInteger ------------ Graham Klyne GK(a)NineByNine.org

6 9

Lazy IO and 'safe' uses of 'unsafePerformIO'
by Matthias Mann 08 Oct '03

08 Oct '03

Recently, there has been some discussion on this list about ongoing research on the role of unsafePerformIO, lazy IO and evaluation strategies. Within our research group at JWG-University Frankfurt some work has been done concerning the development of a non-deterministic call-by-need lambda calculus FUNDIO as a semantic basis for HasFuse, a modified implementation of the Glasgow Haskell Compiler which compiles Haskell programs using 'unsafePerformIO' in a 'safe' way, i.e. deploys only those optimizations that have been proven correct w.r.t. FUNDIO. In this context, experience with GHC's implementation has shown up that if compiled with ghc -O0 -fno-do-lambda-eta-expansion while avoiding INLINE-pragmas, 'most' uses of unsafePerfomIO are 'safe' in the sense of FUNDIO's contextual equivalence. For further details, downloads of papers and sources, please refer to the project WWW page http://www.ki.informatik.uni-frankfurt.de/research/diamond The results of FUNDIO show how evaluation may be interleaved with direct-call IO. In particular not only (\xs -> let z = length xs in "Hello World\n") _|_ = "Hello World\n" is a valid equation in FUNDIO, but also for an arbitrary expression t which may involve direct-call IO the equation (\xs -> let z = length xs in "Hello World\n") t = "Hello World\n" holds. Furthermore, the investigations indicate that some kind of optimistic evaluation is possible, i.e. the expression t above could be evaluated as long as no IO in t is executed. Hence, a demand-driven style for IO could be achieved. Matthias Mann JWG-University Frankfurt

1 0

odd interactions (was: IO behaves oddly if used nested)
by C.Reinke 07 Oct '03

07 Oct '03

[moved to haskell-cafe] > The odd is in the conceptual explanation. If I give a description > of some f x = y function in Haskell I expect that some program f x > is reduced to y and the result is given back (possibly printed). A > good story to sell to students. > > This is almost everywhere the case except for the IO monad. indeed. Although, for the benefit of your students, you'll want to separate printing and reduction, even in the first case. The important thing to realise here (and to pass on to your students) is that input/output-interactions and functional program reductions are two conceptually very different things, and that this difference is independent of which of the many functional I/O systems you use. So you can not use the functional reduction explanation for I/O as well. Once upon a long ago, I had to add IO to a purely functional reduction system as part of my PhD work, and to clarify things for myself, I tried to express the various available functional I/O systems in the common framework of transformation rules (program reduces to program, state transforms into state). The difference then simply became one of context-free versus context-sensitive transformations. [summarised in chapter 3 of my old thesis http://www.cs.kent.ac.uk/people/staff/cr3/publications/phd.html perhaps you can find some useful suggestions there?] The differences between character streams, request/response streams, result continuations, monadic I/O, or even uniqueness-typed environment passing are merely differences in how the context-free functional program reductions are embedded in a context-sensitive environment of I/O devices. They each have their pros&cons (the chapter tries to outline a logical development between the systems), and they all try to embed functional reductions into their I/O context in such a way that doing I/O does not look too foreign. So, each of the functional I/O systems lets you play down the difference between context-sensitive input/output and functional reductions to some extent, but in each of the systems, you quickly run into trouble if you try to take the similarities too far. > 3* Hmm, feels like math, looks like math, ahah! is math! > (designers and thinkers) Making the distinction between context-free and context-sensitive transformations explicit should help your group 3, as it gives them an operational semantics view of what their programs mean, and what they are supposed to do. > from what they expect. The usual questions of group 3: > > * Why is an IO a evaluated if I am not interested in it's result? > (opposite to the f x = y lazy behavior) main is evaluated because you asked the system to run its value (the whole IO a, not the a-typed result returned by running it). > * Why is in the putStr "hello world" example Hello World not shown? > (opposite to expected f x = y eval-first-then-show behavior) implementation deficiency. a more complete implementation might permit you to show intermediate steps in the program+device state transformation: program || device context =============================================== putStr ("hello "++"world") || <nothing here> -context-free reductions-->* putStr "hello world" || <nothing here> -context-sensitive interaction--> return () || "hello world" Just before the interaction, "hello world" is part of the program, so a step-by-step implementation might show it (you couldn't show it without implementation help, as the IO type is abstract), but after the interaction, the string has moved from the program to the device context in which it the program is running. The string appears on some output device, the implementation could show you return () as the final value of your program (the reduction system I was working with did so). > * Why is in the IO (IO ()) example the inner IO () not evaluated? (somewhat > opposite to expected f (f x) behavior - I personally wonder if it is even > sound in a category theoretical setting) urgh,please.. categories do not need a theory about everything [ducks quickly;] first: in an expression of type IO (IO ()), there is not necessarily an inner IO (). Evaluating the expression, and running the result, will fail or return an IO (), but that might not even exist beforehand (that's just the good old no String in IO String). second: the inner IO () returned by running the outer IO (IO ()) is not evaluated unless needed, and it won't be needed unless run. To run any IO a-typed expression, the current monadic I/O system requires it to be placed at the boundary between your functional program and the I/O context it is running in, i.e., it has to be part of the sequence of IO-operations that make up the value of main. Until it gets run this way, it's just an expression that could evaluate to an IO-script that could be run. > * ...Lots of other questions... better than individual answers is a simple conceptual model that allows the students to answer such questions (and any others they might run into). > Hmm, have to finish this email now - time constraints. I guess the short > story just is: IO monads == sometimes bad conceptual story to sell. no. and especially not to that group of students. but for this group, you can't brush the difficulties under the carpet, as you can with the other groups (and Haskell's I/O system and sugar were designed to be easy on the first two groups). you have to give them something more to wrap their minds around. > A nice (old) idea would be to represent IO as programs which are > interpreted by some _outside_ RTS in a given manner, and leave the > Haskell language clean. That is a valid operational semantics, if you get the interleaving right. That it isn't the most efficient implementation shouldn't matter in a functional programming introduction. > (It might even be a good idea with respect to the compiler > implementation since it removes checking against unsafe IO > behavior from the compiler -- just a thought) Simpler implementation is often not more efficient implementation. Hth, Claus

2 1

Naive instantiation
by Dusan Kolar 07 Oct '03

07 Oct '03

Hello, I've got (maybe a bit naive) question, whether it is possible to have instance of class (already derived from another class) if it uses more concrete type than instances of predecesing classes. Let us assume the following example: class A a where... class (A a) => B a where... class (B a) => C a where... data MyData a = MD Int a instance A (MyData a) where... instance B (MyData a) where... instance C (MyData Int) where... Hugs/GHCi produce errors, of course. Nevertheless, is there any way to obtain such a feature? (In this example, classes A and B represent "abstract" classes providing functions with general algorithms, while class C cannot have a general implementation and requires a concrete data type for MyData.) Thank you for any hints, Dusan

2 1

Read and Write to Same File
by kuq32tr02＠sneakemail.com 07 Oct '03

07 Oct '03

I am writing a program that reads and writes to the same file. I was having some problems with it writing to the file before it read it. I solved it in the following two ways: 1. main = do text <- readFile "test" let something = somefunc text writeFile "test2" something renameFile "test2" "test" 2. main = do text <- readFile "test" let something = somefunc text writeFile "test" $! something Are both of these correct (guaranteed to give the behavior I want)? Which is better (and why)? Thanks!

4 3

how is Haskell pronounced?
by David Roundy 06 Oct '03

06 Oct '03

The subject says it all. I've been using haskell for over a year, but I have no idea how to pronounce it. I tend to oscillate between rhyming with "fell" and rhyming with "full". In the former case the accent goes on the second syllable as in "Pascal", while in the latter case it goes on the first, as in "rascal" or "tattle". I feel silly telling people what a great language it is, when I can't even pronounce its name... :) -- David Roundy http://www.abridgegame.org/darcs

2 1

Why does this work - haskell mysteries?
by Petter Egesund 05 Oct '03

05 Oct '03

Hi; the proof of the pudding does lies in the eating... but I still wonder why this code is working (it is taken from the book "The Craft of functional programming"). The program connects a variable-name to value. The fun initial gives the initial state, update sets a variable & value reads a value). I evaluate value my_store 'b' to 5 and value my_store 'a' to 3 as expected from the text in the book. But I can't see what is happening here. The book has a parallel example where the data is held in a list, and this version is easy to follow, but this trick with storing a lambda-function inside a newtype beats me. The problem is that I do not understand where the accumulated data is stored (not in a list - it seems like something like a chain of functions which can be pattern-matched, but I am not sure). And why does not the lambda-function (\w -> if v==w then n else sto w) start a endless loop? (This is not homework - I am a programmer who is curious about Haskell!) Any clues, anyone? Cheers, Petter -- Var is the type of variables. type Var = Char newtype Store = Sto (Var -> Int) -- initial :: Store initial = Sto (\v -> 0) value :: Store -> Var -> Int value (Sto sto) v = sto v update :: Store -> Var -> Int -> Store update (Sto sto) v n = Sto (\w -> if v==w then n else sto w) -- testit -- my_store = update (update (update initial 'a' 4) 'b' 5) 'a' 3)

4 5

Re: lexer puzzle
by Brandon Michael Moore 05 Oct '03

05 Oct '03

Note I've replied to haskell-cafe. This post is a bit chatty and low on solid answers. On Thu, 25 Sep 2003, Sean L. Palmer wrote: > > >>A... should be split into "A.." and "." > > >I found a compromise: let's make it a lexing error! :-) > > At least that agrees with what some Haskell compilers implement. No > > current Haskell compiler/interpreter agrees with what the report seems > > to say, that is that "A..." should be lexed as the two tokens "A.." and > > ".", and similarly, "A.where" should be lexed as "A.wher" followed by "e". > > Hi. I'm really new to Haskell, just learning it, and I must say I'm pretty > overwhelmed by the large variety of constructs. (=>, <-, \ to name a few) Would that be \ as in TREX row variable polymorphism? Just remember most operators are just library functions. It's only =, ->, =>, <-, :: that are really part of the language, and {,},; for grouping. Did I miss any? > > But I'm just writing this to let you guys know (surely you know this > already) that anyone from a C/C++/Java/Delphi background is going to > completely misunderstand the meaning of A.anything in Haskell... it's > completely nonintuitive to people with my background. I kinda like dot > notation because it ties together the symbols visually, for instance > "myrec.myfield" is more of a unit than "myrec myfield". It stays together > better when surrounded by other code, and would result in fewer parenthesis > necessary. A Python programmer would understand instantly: Python uses exactly the same syntax for module access, though Python modules are usually in lowercase. It also seems to be very much in the spirit of "access a member of this object" of an OO language. Or was that supposed to be composition of a constructor with a function, A . f? Function composition, and higher order functions in general are likely to confuse an imperative programmer, but I think there isn't much syntax can do there. Or are you talking about the field access syntax? Maybe the problem is that dot has two to five different meanings, function composition, naming module members, building hierarchial module names, being a decimal point, and making elipses, and is commonly used for yet another purpose in OO languages. > Haskell to me seems to be a great language with a syntax problem, and a bad > case of too many ways to do the same thing; thus every programmer does > things their own way and it's difficult to grasp the language by looking at > various programs, since they're all so very different. As a small example, > there's 'let' vs. 'where'. Maybe a bit of pruning would be in order. Do you mean the syntax is bad in places? Haskell is the cleanest language I know of, but I'm sure it has some grungy bits. I've had problems with unary minus (can't slice binary minus), and precedence of with irrefuatble patterns and type ascription. I would be happy for any confusing syntax to be improved. Any good ideas? Syntax change is a possibility: do notation is a relatively recent addition, and arrow syntax is in the works. I think you might instead mean the syntax cuts down our market share because it isn't like common (C derived) languages. I don't think Haskell could borrow any more syntax from C without actually making the language worse. It's a problem, but not with the syntax. If someone is so solidly into a C++/Java/OO mindset that the syntax would be a problem, the semantics would probably be even more of a problem. I would suggest Python if Haskell was too much of a jump for someone. It's still OO, but it encourages more flexible and interesting programs, and you don't have to live in a Java type system. Plus, it has more libraries, bindings, and PR, so it's easier to get permission to use it in a company. If someone is used to Python's layout rule and lack of type signatures, and gets their head around some of the fun you can have dynamically picking which members of an object to access, assigning to __dict__ and so on, then Haskell should be much less of a jump in syntax, and less imposing in semantics. > That said, I still think it looks more promising than any other language > I've looked at that actually is being actively used and maintained and has a > decent installed base and good cross platform support. So I will learn it. > I just wish the transition was easier and that it took less time to learn. > ;) > > Sean I learned Haskell from the "gentle introduction". It seemed gentle enough to me but others disagree, so I'm probably not the best for advice for the raw beginner. If you are interested in learning about monads though, Jeff Newbern's monad tutorial seems accessible and as complete as anything this side of Phil Wadler's paper. I hope learning Haskell goes well. Brandon

7 8

Re: Read and Write to Same File
by kuq32tr02＠sneakemail.com 05 Oct '03

05 Oct '03

> > main = do text <- readFile "test" > > let something = somefunc text > > writeFile "test" $! something > > There is no guarantee that $! will force evaluation of the entire > 'something', so you can start writing to file before you finished > reading from it. Hopefully it will cause an exception (like in GHC), > otherwise you could damage your data (like in Hugs). > > PS. How does it behave in NHC? This is the version I've been using for a while now. It runs perfectly fine in both GHC and Hugs. I've used it many, many times with no noticeable problems. Should I be seeing errors (like exceptions in GHC)? I don't have NHC installed, so I can't test it. Thanks!

1 0

Re: IO behaves oddly if used nested
by Derek Elkins 05 Oct '03

05 Oct '03

On Sat, 04 Oct 2003 13:13:59 +0200 "blaat blaat" <l4t3r(a)hotmail.com> wrote: [moved to Haskell-Cafe] > > Neither example is odd behavior, unless > >you consider Hugs providing a perfectly reasonable instance of Show > >for IO a odd. > > True, every program behaves exactly as according to the definition of > the run-time behavior of Haskell programs. (Hugs deviates a bit from > ghc but ah well) The odd is not in the run-time behavior. > > The odd is in the conceptual explanation. If I give a description of > some f x = y function in Haskell I expect that some program f x is > reduced to y and the result is given back (possibly printed). A good > story to sell to students. Then use an impure language like Scheme. This is exactly what the IO monad avoids. > This is almost everywhere the case except for the IO monad. This is never the case. You can -only- print things via the IO monad. > In the former example, the inner putStr is _not_ evaluated but a > message is shown (hinting that a IO has some structure we can observe > before evaluation). The message shown doesn't expose any structure, let alone suggest that you can observe it. The message is independent of the actual IO action it only uses the type. You could write the Show instance yourself. instance Show (IO a) where show _ = "<<IO action>>" > In the latter example, it is shown that we are not > interested in a result of a IO program, but only in its (lazily > generated) side-effects. The effects aren't lazily generated. Monads are independent of evalution order. They would work just as well in a strict language. This is what makes them pure. (See Amr Sabry's "What is a Purely Functional Language?") > The monad behaves oddly with respect to the f > x = y behavior. Not really. If f x were, f x = \_ -> unsafePerformIO (putStr "Hello") would you be surprised that f 5 doesn't print "Hello"? > I think I observe the following reactions when I explain IO: Perhaps because you don't explain it properly? > * Why is an IO a evaluated if I am not interested in it's result? > (opposite to the f x = y lazy behavior) It isn't. If you are interested in it's result, then the result is an action which will do whatever -when run-, -not- the side-effects. If you aren't interested in it's result it will never be evaluated in Haskell, but even if it were (by adding a seq or using a strict language) the result would -still- be an action that will do something -when run-, and since you aren't interested in it it will be discarded without ever executing; a good thing as this maintains purity. > * Why is in the putStr "hello world" example Hello World not shown? > (opposite to expected f x = y eval-first-then-show behavior) Because it is never run. > * Why is in the IO (IO ()) example the inner IO () not evaluated? Because it is never run. > (somewhat opposite to expected f (f x) behavior - I personally wonder > if it is even sound in a category theoretical setting) As for the Category Theoretic behavior, it's perfectly sound. The RTS just discards the result, given that in a sense it's type is IO a -> something where 'a' is not free in something, all it -can- do is discard the result by parametricity. It doesn't matter if it 'a' is Int, (), IO FooBar, Char-> Int or anything else, any more than it matters in what type or value the first argument is in f _ = () or the "return" type of the monad action m in do_ <- m;return() (or written another way, m >>= \_ -> return ()). If you think of IO actions as state transformers (which has it's faults but works for this), then the observed behavior makes perfect sense. None of the IO actions -can- execute because they don't have the state of the world to process. It's just like with the State monad, execState (do x <- get;put (x+5);return (put 10)) 0 returns 5 not 10, the state (0 then 5) is never passed to put 10. This can be seen by unfolding this into the standard state-passing definition. If we take out the execState, -nothing- happens and we just get functions that will transform a state once it's provided; they won't and -can't- do anything until that state is provided. So putStr "foo" is IO () is World -> ((),World), it is not surprising that f _ = 10, f (putStr "foo") does not print "foo", anymore than it is surprising that f (\x -> undefined) does not cause an error, or f (put 10) does not change some state somewhere.

2 1