July 2004 - Haskell-Cafe

Ambiguous type variable
by Arjun Guha 27 Jul '04

27 Jul '04

Hi, I'm new to Haskell and am getting this error: AlphaBeta.hs:1: Ambiguous type variable `v' in the top-level constraint: `Ord v' arising from use of `maxValue' at AlphaBeta.hs:12 in the following code: module AlphaBeta where -- Game states are instances of MinimaxState class MinimaxState st where successors:: st -> [(action,st)] terminal:: st -> Bool utility:: (Ord v) => st -> v minimaxDecision state = filter (\(_,st) -> utility st == v) (successors state) where v = maxValue state maxValue:: (MinimaxState state, Ord v) => state -> v maxValue state = if terminal state then utility state else (foldl max x xs) where (x:xs) = map (minValue.snd) (successors state) minValue:: (MinimaxState state, Ord v) => state -> v minValue state = if terminal state then utility state else (foldl min x xs) where (x:xs) = map (maxValue.snd) (successors state) Any hints would be appreciated. -Arjun

4 4

RE: [Haskell-cafe] Parsec Problem
by Bayley, Alistair 27 Jul '04

27 Jul '04

> I copied this example exactly from the page > http://www.cs.uu.nl/people/daan/download/parsec/parsec.html > > price = lexeme (do{ ds1 <- many1 digit > ... > However attempting to compile it gives the error message > ... > I wish I knew what that meant. If someone could explain it > and tell me what's wrong, I'd appreciate it. The documentation for Parsec is a bit out-of-date; some things still work as described, and some things have changed. You'll have to browse the current libraries at the same time as reading the Parsec documentation to determine if a particular feature is still working as described, or if there's a newer (better?) way of doing the same thing. If you want to learn how to use the libraries, I recommend writing some very simple character/string parsers first, to see how the combinators work. Back to your parser... A lexeme parser (as described in the Parsec document) is one that consumes any trailing whitespace after the token has been read, so as to leave the next non-whitespace token ready on the input stream. The easiest way to fix the price parser is simply to add Text.ParserCombinators.Parsec.Char.spaces after the last digits have been read. price = do { ds1 <- many1 digit ; char '.' ; ds2 <- count 2 digit ; spaces -- eat trailing whitespace ; return (convert 0 (ds1 ++ ds2)) } <?> "price" where convert n [] = n convert n (d:ds) = convert (10*n + digitToInt d) ds (The lexeme function is now a record field accessor in Text.ParserCombinators.Parsec.Token. There is a data type called TokenParser, of which lexeme is one field. There's probably a way to write the price parser using TokenParser and the lexeme function/field, but I haven't figured this out yet.) Alistair. ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

Re: [Haskell-cafe] Parsec Problem
by J.Garrett.Morris＠Dartmouth.EDU 27 Jul '04

27 Jul '04

--- haskell(a)alias.spaceandtime.org wrote: I wish I knew what that meant. If someone could explain it and tell me what's wrong, I'd appreciate it. --- end of quote --- Lexeme is actually a selector function over the TokenParser record. In the previous section (also on lexical analysis), he included the code: module Main where import Parsec import qualified ParsecToken as P import ParsecLanguage( haskellStyle ) lexer :: TokenParser () lexer = makeTokenParser (haskellDef { reservedOpNames = ["*","/","+","-"] }) whiteSpace= P.whiteSpace lexer lexeme = P.lexeme lexer -- <-- here's lexeme symbol = P.symbol lexer natural = P.natural lexer parens = P.parens lexer semi = P.semi lexer identifier= P.identifier lexer reserved = P.reserved lexer reservedOp= P.reservedOp lexer Once you've done that, the sample code should work fine. /gXm

1 0

Type Theory? Relations
by haskell＠alias.spaceandtime.org 26 Jul '04

26 Jul '04

Hello, I have a question that may pertain to type theory. According to Enderton, one of the ways to define an ordered pair (a,b) is {{a},{a,b}}. A relation is defined as a set of ordered-pairs. A map, of course, is a single-valued relation. Given all that, suppose I have a "FiniteMap Int String" in Haskell. This is, according to the definitions above, a "Set (Int,String)". An element of that has type (Int,String), which contains {Int,String}. But that can't exist because a Set contains only elements of one type. What I'm getting at is that it seems that a Relation should be defined type Relation a = Set (a,a) rather than type Relation a b = Set (a,b) so that we don't have this problem. Thanks.

2 1

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 26 Jul '04

26 Jul '04

As far as I understand it haskells lazy evaluation resembles dataflow computation - IE values are computed on demand. This problem has already been solved for hardware, you end up with what is termed a super-scalar architecture. Instructions read from memory fill a re-order buffer. As computations complete value slots in the reorder buffer are filled with the result values. When an instruction has all its values it can be executed, and will be assigned to the next available execution unit. I am not too sure of the internal architecture of GHC, but I can imagine that funtions waiting to be run will have slots for arguments, that will be filled in when values become available. The whole point is that a function with three parameters can spark three threads to calculate each parameter without worrying about the side affects of each function. No locking is necessary because you only spark one thread for each argument. I suspect I haven't fully understood the difficaulty in doing this, care to enlighten me? Keean.

1 0

Re: [Haskell-cafe] optimising for vector units
by Jon Cast 26 Jul '04

26 Jul '04

Ketil Malde <ketil+haskell(a)ii.uib.no> wrote: > MR K P SCHUPKE <k.schupke(a)imperial.ac.uk> writes: <snip> > One would expect a lazy and pure language Not lazy! See below. > to be excellent for parallelization, since the programmer is generally > removed from the actual flow of execution anyway. At some point (for > some n), being able to spawn n threads will gain you more than a > factor c constant overhead, ^^^^^^^^^^^^^^^^^^^^^^^^^^ What makes you think the overhead is constant? Without Optimistic Evaluation, Haskell programs mutate /heavily/, and even with Optimistic Evaluation I'm sure there is some mutation going on. With a truly parallel system, every mutation has to be locked in some way; reducing the number of locking operations to merely constant overhead is an interesting (as in extremely difficult) research problem. > and Haskell programs, with a run-time system that can evaluate > expressions in paralllel, will outperform single threaded C code. > > (But it probably isn't that simple, or we would have it already :-) Nope. Jon Cast

2 1

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 26 Jul '04

26 Jul '04

>Correct me if I'm wrong but I thought that there was some overhead to >making FFI (even safe/unsafe) You are not wrong... so it would only be worth it if you could execute a whole bunch of C at the same time. But it is possible... Consider: Use a monad to sequence vector operations on the Vector class. The monad instead of directly executing vector instructions compiles a syntax tree, or a list of instructions. This list of instructions is passed to the C code, which sequences the primitive vector ops into a block of code, and returns a function pointer via the FFI. You just call the whole block with the right parameters. This is probably getting to be more work than integrating stuff into GHC though. It is also doing stuff dynamically that could be done statically at compile time. If GCC is providing vector abstractions then it would seem a lot less work for GHC to incorporate 'vector' types directly... Anyone like to comment more specifically on what would be involved in plumbing a new datatype into GHC that handles vectors? Assuming we wanted an interface like: myFn :: Vector Word8 Four -> Vector Word8 Four. Also vector is not a good name, as with vectors: "a * b" would be the cross-product, but with SIMD we get 4 scalar multiplies... Keean.

1 0

optimising for vector units
by Matthew Roberts 26 Jul '04

26 Jul '04

Hi, Does anybody know if any of the Haskell compilers are able to optimise for vector units (like MMX, SSE(2), 3D_Now! and AltiVec)? My investigations have revealed that c requires special programming constructs to make the most of these processor capabilites (i.e. the compiler is not able to work it out for itself). Is there any work on getting haskell compilers to work this kind of thing out? Cheers, Matt

3 2

Trouble with types
by Kari Pahula 23 Jul '04

23 Jul '04

I'm new to Haskell, as you can probably tell... I have the following data types: data Real a => Energy a = Energy a deriving (Eq, Ord, Show) data Real a => HeatC a = HeatC a deriving (Eq, Ord, Show) data Object h c = Object {energy :: (Energy h), heatc :: (HeatC c)} deriving (Eq, Show) data Real a => Temp a = Temp a deriving (Eq, Ord, Show) I'd like to make a function to calculate the temperature of an object. Physically this is the total heat times the heat capacity. I tried this with the following: temp :: (Real a) => Object (Energy a) (HeatC a) -> Temp a temp Object (Energy e) (HeatC c) = Temp e*c But this fails in hugs with: ERROR "temp.hs":22 - Constructor "Object" must have exactly 2 arguments in pattern What's the syntax to use here? Should I do this in some other way? Should I use newtype here instead of data?

4 4

Re: generalised algebraic data types, existential types, and phantom types
by Jim Apple 23 Jul '04

23 Jul '04

I tried to post this to gmane.comp.lang.haskell.general, but it never got there - it may belong here anyway. Abraham Egnor wrote: > Is there any closer approximation [of GADTs] possible? {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} data Term a = forall b . (EqType a b, EqType b Int) => Lit Int | forall b . (EqType a b, EqType b Int) => Inc (Term Int) | forall b . (EqType a b, EqType b Bool) => IsZ (Term Int) | If (Term Bool) (Term a) (Term a) | forall b . Fst (Term (a,b)) | forall b . Snd (Term (b,a)) | forall b c . (EqType a (b,c))=> Pair (Term b) (Term c) class EqType a b | a->b, b->a instance EqType a a Unfortunately, I can't seem to write an eval function: eval (Lit a) = a gives Inferred type is less polymorphic than expected Quantified type variable `b' is unified with `Int' When checking an existential match that binds The pattern(s) have type(s): Term Int The body has type: Int In the definition of `eval': eval (Lit x) = x Any ideas? Jim

2 1