- Haskell-Cafe - Haskell.org

Associated types and data constructors (was: the MPTC Dilemma (please solve))
by David Menendez 20 Mar '06

20 Mar '06

(I've moved this from haskell' to haskell-cafe, because it's more a question about associated types than about resolving the MPTC dilemma.) Bulat Ziganshin writes: > Hello Manuel, > > MMTC> My statement remains: Why use a relational notation if you can > MMTC> have a functional one? > > how about these examples? > > MMTC> class Monad m => RefMonad m where > MMTC> type Ref m :: * -> * > > can i use `Ref` as type function? for example: > > data StrBuffer m = StrBuffer (Ref m Int) > (Ref m String) > This is something I've been wondering about for a while. Can you do that sort of thing with associated types? As another example, consider this type class for composible continuation monads: class Monad m => MonadCC p sk m | m -> p sk where newPrompt :: m (p a) pushPrompt :: p a -> m a -> m a withSubCont :: p b -> (sk a b -> m b) -> m a pushSubCont :: sk a b -> m a -> m b You can use instances of this class to create backtracking monads, along these lines: data Tree m a = HZero | HOne a | HChoice a (m (Tree m a)) newtype SR p m a = SR (forall ans. ReaderT (p (Tree m ans)) m a) instance MonadCC p sk m => MonadPlus (SR p m) With associated types, the MonadCC class becomes: class Monad m => MonadCC m where type Prompt m a type SubCont m a b newPrompt :: m (Prompt m a) pushPrompt :: Prompt m a -> m a -> m a withSubCont :: Prompt m b -> (SubCont m a b -> m b) -> m a pushSubCont :: SubCont m a b -> m a -> m b Since |Prompt m| is determined by |m|, can we eliminate the prompt parameter from SR? newtype SR' m a = SR' (forall ans. ReaderT (Prompt m (Tree m ans)) m a) instance MonadCC m => MonadPlus (SR' m) That would presumably lead to SR' having the type SR' :: (MonadCC m) => ReaderT (Prompt m (Tree m ans)) m a -> SR' m a That doesn't seem like it should be a problem, since it's impossible to create a value of type |ReaderT (Prompt m (Tree m ans)) m a| unless m is an instance of MonadCC, but it also puts a context on a newtype data constructor, which isn't currently allowed. Sure, it's still possible to do this: instance MonadCC m => MonadPlus (SR (Prompt m) m) but that doesn't feel like a big win. -- David Menendez <zednenem(a)psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"

1 0

STUArray
by Frederik Eaton 19 Mar '06

19 Mar '06

Hi all, I'm trying to figure out how to use STUArray. Is it possible to let it be polymorphic? Here is an excerpt from my program: class (IArray UArray k, Ord k, Fractional k) => Elt k class (Bounded a, Enum a, Ix a, Eq a, Show a) => IxB a -- |like Array but uses IxB instead of Ix newtype Vector k i = Vector (UArray.UArray i k) deriving (Eq) margin :: (IxB a, IxB b, Elt k, (MArray (STUArray s) k (ST s))) => Vector k a -> (a -> b) -> Vector k b margin (Vector v) f = Vector (runSTUArray (do ax <- newArray (minBound, maxBound) 0 mapM_ (\ (i,x) -> updateArray ax (f i) (+x)) (assocs v) return ax )) where updateArray ax i f = do e <- readArray ax i writeArray ax i (f e) When I try to run it, I get the following error. I think I understand what the error means, but not how to fix the problem: Vector2.hs:166:22: No instance for (MArray (STUArray s) k (ST s)) arising from use of `updateArray' at Vector2.hs:166:22-32 Probable fix: add (MArray (STUArray s) k (ST s)) to the expected type of an expression or add an instance declaration for (MArray (STUArray s) k (ST s)) In a lambda abstraction: \ (i, x) -> updateArray ax (f i) ((+ x)) In the first argument of `mapM_', namely `(\ (i, x) -> updateArray ax (f i) ((+ x)))' In a 'do' expression: mapM_ (\ (i, x) -> updateArray ax (f i) ((+ x))) (assocs v) Thanks in advance, Frederik -- http://ofb.net/~frederik/

5 7

RE: [Haskell-cafe] how would this be done? type classes? existentialtypes?
by Geest, G. van den 18 Mar '06

18 Mar '06

Try using a GADT: data Rs where Rs :: Resource a => a -> Rs class Resource a where resourceName :: a -> String instance Resource String where resourceName x = "String" instance Resource Int where resourceName x = "Int" resName (Rs x) = resourceName x resNames = map resName test = resNames [Rs "Hi", Rs (1::Int) ] The most important observations is that when pattern matching on (Rs x) we cannot make any assumptions about x, except using the class members of Resource. We hope this will help you, Gerrit (and the rest of the ST-lab) -----Original Message----- From: haskell-cafe-bounces(a)haskell.org on behalf of Matthias Fischmann Sent: Thu 3/16/2006 12:57 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] how would this be done? type classes? existentialtypes? hi, this is one of those situations that always make scheme and perl hackers laugh at me: i have written a piece of code that is intuitively clear, and now i am trying to turn it into something that compiles. and here it goes. i have a type class that looks something like this: class Resource a where resourceName :: a -> String resourceAdvance :: a -> a resourceStarved :: a -> Bool resourceSpend :: a -> Int -> a resourceEarn :: a -> Int -> a resource types are rice, crude oil, pizza, software code, and so on. they all have a different internal structure and the same abstract interface, that's why i have defined this type class. now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) => [a] but with r1 being pizza, r2 being crude oil, and so on. my first idea was this: data Rs = forall a . (Resource a) => Rs a unRs (Rs a) = a rsName :: Rs -> String rsName = resourceName . unRs ... and then export Rs as an abstract data type. this would allow for lists of type [Rs], which is exactly what i want. but what is the type of unRs? or better: can i make it type at all? and isn't this solution a little redundant and verbose? should i do it like in the example for existentially quantified types in the ghc manual? http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html but wouldnt't the code become really messy? or should i do the type class and instances, and then do Rs the existentially quantified way, with all class methods arguments to the Rs constructor? or is there a completely different way to do this (besides using scheme or perl :-)? thanks, matthias -----Original Message----- From: haskell-cafe-bounces(a)haskell.org on behalf of Matthias Fischmann Sent: Thu 3/16/2006 12:57 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] how would this be done? type classes? existentialtypes? hi, this is one of those situations that always make scheme and perl hackers laugh at me: i have written a piece of code that is intuitively clear, and now i am trying to turn it into something that compiles. and here it goes. i have a type class that looks something like this: class Resource a where resourceName :: a -> String resourceAdvance :: a -> a resourceStarved :: a -> Bool resourceSpend :: a -> Int -> a resourceEarn :: a -> Int -> a resource types are rice, crude oil, pizza, software code, and so on. they all have a different internal structure and the same abstract interface, that's why i have defined this type class. now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) => [a] but with r1 being pizza, r2 being crude oil, and so on. my first idea was this: data Rs = forall a . (Resource a) => Rs a unRs (Rs a) = a rsName :: Rs -> String rsName = resourceName . unRs ... and then export Rs as an abstract data type. this would allow for lists of type [Rs], which is exactly what i want. but what is the type of unRs? or better: can i make it type at all? and isn't this solution a little redundant and verbose? should i do it like in the example for existentially quantified types in the ghc manual? http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html but wouldnt't the code become really messy? or should i do the type class and instances, and then do Rs the existentially quantified way, with all class methods arguments to the Rs constructor? or is there a completely different way to do this (besides using scheme or perl :-)? thanks, matthias

3 3

Re: dynamic arrays
by Jared Updike 18 Mar '06

18 Mar '06

(Moved to haskell-cafe) JU> General question to the list: JU> (Q) Are there any data structures in Haskell similar to C++/STL JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. JU> List<int>)? These data structures grow automatically as you add JU> elements to them (but in large chunks, not one node at a time). This JU> data structure (if it exists in Haskell) would run inside a monad (ST JU> and/or IO) and it would automaticly resize when needed, but would be JU> more or less like a mutable array except you can add new elements to JU> the end of it without reallocating an entire array of n+1 elements... i tried to implement this today :) but there is one problem: > if i have (l,u) - array bounds of type Ix, and i - offending index of > the same type, how can i compute new bounds of array so that it will > grow in large chunks? there is no such computation operations for > Ix type and that is logical - if this array is really a matrix then > it's hard to use the same rules of extending it as for vectors Hmmm, that is a problem, especially as you said, for enum types that are bounded above. I guess you can't make it grow more than the min and max. For the most part, this dynamic array would only be useful for arrays with indices isomorphic to the natural numbers. > such computation as (u-l)*2+l is great for integral indexes, but not > for general case. now i plan to use this strategy for all enum types > and just "grow to minimal and maximal indexes actually used" for other > index types Perhaps the function to build these DynamicArrays could take a Maybe parameter telling the maximum possible range (for bounded enums) or Nothing if the array is allowed to grow indefinitely. Or an Either parameter where Left (a,a) tells the max range and Right (a,a) -> (a,a) which tells how the range should grow on a resize. Or just the range resize function :: (a,a) -> (a,a) telling how to grow on a resize, i.e. for enums function = id. Something like that. Jared.

4 5

different code in different platforms
by José Miguel Vilaça 17 Mar '06

17 Mar '06

Sorry. In the previous email I forgot the subject. Hi Im having a small problem with the portability of my Haskell code. My code uses wxHaskell and the library for which this one is the Haskell interface (that is called wxWidgets) doesnt work in the same away in Windows and Linux. Now I now which code run in Linux and in Windows but I dont want to have to manually change the file in each platform. I tried a solution using the C pre-processor but I getting in trouble. I use code like: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif I also add the --cpp to the ghc and it works for me in Linux but give me linking errors in Windows. Does someone have any hints on how to have different code in Windows and Linux? I would be thankful in some help. Best regards Miguel Vilaça

5 4

Re: [Haskell-cafe] how would this be done? type classes? existential types?
by Matthias Fischmann 16 Mar '06

16 Mar '06

Alexandra Silva <xana(a)di.uminho.pt> wrote: > http://homepages.cwi.nl/~ralf/HList/ this looks like it might address my problems with Read / Eq instantiation? will read. thanks again to everybody. m.

1 0

Learning from scratch
by Xavier Elizalde 16 Mar '06

16 Mar '06

I'm just starting to learn Haskell from scratch and I've just hit a snag. The book "Haskell: The Craft of Functional Programming, Second Edition" uses some examples that call functions from Prelude.hs. But for some reason, two installations of Haskell that I have on my computer don't have the functions available. I have the OS X version of Hugs (http://www.haskell.org/soe/software.htm) for the book "The Haskell School of Expression" installed, as well as the latest version of the Glasgow Haskell Compiler. Both of them get errors with the functions such as "ord" and "chr" mentioned at the beginning of the first book mentioned. Where can I get Prelude.hs and the other files it needs, and what do I do with them? I'm going to move on to the School of Expression book after the Craft of Functional Programming book, which is why I have the SOE version of hugs installed.

2 1

(no subject)
by José Miguel Vilaça 16 Mar '06

16 Mar '06

Hi Im having a small problem with the portability of my Haskell code. My code uses wxHaskell and the library for which this one is the Haskell interface (that is called wxWidgets) doesnt work in the same away in Windows and Linux. Now I now which code run in Linux and in Windows but I dont want to have to manually change the file in each platform. I tried a solution using the C pre-processor but I getting in trouble. I use code like: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif I also add the --cpp to the ghc and it works for me in Linux but give me linking errors in Windows. Does someone have any hints on how to have different code in Windows and Linux? I would be thankful in some help. Best regards Miguel Vilaça

2 1

request for code review
by Shannon -jj Behrens 16 Mar '06

16 Mar '06

Hi, I'm working on another article like <http://www.linuxjournal.com/article/8850>. This time, I'm taking an exercise out of "Expert C Programming: Deep C Secrets" and translating it into Haskell. The program translates C type declarations into English. I would greatly appreciate some code review. I'd prefer to look like an idiot in front of you guys rather than in front of everyone in the world! ;) Please understand, I am not a Haskell expert! Therefore, please make your suggestions simple enough that I can actually accomplish them! By the way, my code *mostly* follows the code laid out in the book. I don't use a lexer or a parser or greatly improve on his algorithm. I'd like the Haskell and C versions to be similar so that they can be compared. The C version is: <http://www.cs.may.ie/~jpower/Courses/compilers/labs/lab3/parse_decl.c> The Haskell version is below. Thanks! -jj {- Translate C type declarations into English. This exercise was taken from "Expert C Programming: Deep C Secrets", p. 84. Example: echo -n "int *p;" | runhugs cdecl.hs Name: Shannon -jj Behrens <jjinux(a)gmail.com> Date: Fri Feb 17 00:03:38 PST 2006 -} import Char (isSpace, isAlphaNum, isDigit) -- |> is like a UNIX pipe. infixl 9 |> x |> f = f x data TokenType = Identifier | Qualifier | Type | Symbol Char deriving (Show, Eq) data Token = Token { tokenType :: TokenType, tokenValue :: String } deriving Show data ParseContext = ParseContext { input :: String, -- The input that has not been parsed yet. output :: [String], -- A list of strings in the reverse order of that which -- they should be printed (e.g. [" a dog.", "I have"]). currTok :: Token, -- The current token, if defined. stack :: [Token] -- A stack of tokens we haven't dealt with yet. } deriving Show -- For convenience: currTokType :: ParseContext -> TokenType currTokType ctx = ctx |> currTok |> tokenType currTokValue :: ParseContext -> String currTokValue ctx = ctx |> currTok |> tokenValue type ParseContextTransformation = ParseContext -> ParseContext -- Start a new ParseContext given an input string. createParseContext :: String -> ParseContext createParseContext input = ParseContext {input=input, output=[], stack=[]} -- Create the final output string given a ParseContext. consolidateOutput :: ParseContext -> String consolidateOutput ctx = ctx |> output |> reverse |> concat {- "Write" to a ParseContext's output. The API is a bit strange. (writeOutput s) is itself a ParseContextTransformation which you can apply to ParseContexts. Strange but convenient. -} writeOutput :: String -> ParseContextTransformation writeOutput s = \ctx -> let newOutput = s : (output ctx) in ctx {output=newOutput} -- Return the top token on the stack. stackTop :: ParseContext -> Token stackTop ctx = let (x:xs) = stack ctx in x -- Pop the stack. pop :: ParseContextTransformation pop ctx = let (x:xs) = stack ctx in ctx {stack=xs} -- Write the value of the top of the stack and then pop it. popAndWrite :: ParseContextTransformation popAndWrite ctx = ctx |> ((stackTop ctx) |> tokenValue |> writeOutput) |> pop -- Classify a string into a Token. classifyString :: String -> Token classifyString "const" = Token Qualifier "read-only" classifyString "*" = Token (Symbol '*') "pointer to" classifyString s@(c:[]) | not (isAlphaNum c) = Token (Symbol c) s classifyString s = Token (whichType s) s where whichType "volatile" = Qualifier whichType "void" = Type whichType "char" = Type whichType "signed" = Type whichType "unsigned" = Type whichType "short" = Type whichType "int" = Type whichType "long" = Type whichType "float" = Type whichType "double" = Type whichType "struct" = Type whichType "union" = Type whichType "enum" = Type whichType _ = Identifier -- Read the next token into currTok. getToken :: ParseContextTransformation getToken ctx@(ParseContext {input=s}) = let lstrip s = dropWhile isSpace s (token, theRest) = s |> lstrip |> lexString in ctx {currTok=token, input=theRest} -- Read a token. Return it and the left-over portion of the string. lexString :: String -> (Token, String) lexString s@(c:cs) | isAlphaNum c = let (tokString, theRest) = span isAlphaNum s token = classifyString tokString in (token, theRest) lexString ('*':cs) = (classifyString "*", cs) lexString (c:cs) = (classifyString (c:[]), cs) -- Put tokens on the stack until we reach the first identifier. readToFirstIdentifier :: ParseContextTransformation readToFirstIdentifier ctx = let afterIdentifier = ctx |> getToken |> pushUntilIdentifier identifier = afterIdentifier |> currTokValue s = identifier ++ " is " in (afterIdentifier {output=[s]}) |> getToken -- Keep pushing tokens until we hit an identifier. pushUntilIdentifier :: ParseContextTransformation pushUntilIdentifier ctx | currTokType ctx == Identifier = ctx | otherwise = let newStack = (currTok ctx) : (stack ctx) in (ctx {stack=newStack}) |> getToken |> pushUntilIdentifier -- Deal with arrays. dealWithArrays :: ParseContextTransformation dealWithArrays ctx = let writeIfNumber ctx = -- Call writeSize if a number. if ctx |> currTokValue |> (!! 0) |> isDigit then ctx |> writeSize |> getToken else ctx writeSize ctx = -- Output the array size. let num = ctx |> currTokValue |> read |> (+ -1) |> show s = "0.." ++ num ++ " " in ctx |> (writeOutput s) in case currTokType ctx of Symbol '[' -> ctx |> (writeOutput "array ") |> getToken |> writeIfNumber |> getToken |> (writeOutput "of ") |> dealWithArrays _ -> ctx -- Recurse until we get past the ['s. -- Deal with function arguments. dealWithFunctionArgs :: ParseContextTransformation dealWithFunctionArgs ctx = let getUntilParen ctx = -- Read tokens until we hit ). case currTokType ctx of Symbol ')' -> ctx _ -> ctx |> getToken |> getUntilParen in ctx |> getUntilParen |> getToken |> (writeOutput "function returning ") -- Deal with pointers. dealWithPointers :: ParseContextTransformation dealWithPointers ctx = case ctx |> stackTop |> tokenType of Symbol '*' -> ctx |> popAndWrite |> (writeOutput " ") |> dealWithPointers _ -> ctx -- Recurse until we get past the *'s. -- Process tokens that we stacked while reading to identifier. dealWithStack :: ParseContextTransformation dealWithStack ctx = case stack ctx of [] -> ctx (x:xs) -> case tokenType x of Symbol '(' -> ctx |> pop |> getToken |> dealWithDeclarator _ -> ctx |> popAndWrite -- Do all parsing after first identifier. dealWithDeclarator :: ParseContextTransformation dealWithDeclarator ctx = ctx |> (case currTokType ctx of Symbol '[' -> dealWithArrays Symbol '(' -> dealWithFunctionArgs _ -> id) |> dealWithPointers |> dealWithStack -- Translate a C type declaration into English. translate :: String -> String translate s = s |> createParseContext |> readToFirstIdentifier |> dealWithDeclarator |> consolidateOutput -- Change this to "show" to debug. -- Main main :: IO () main = do input <- getContents input |> translate |> putStrLn

12 20

Deepest functor [was: fmap for lists of lists of lists of ...]
by oleg＠pobox.com 16 Mar '06

16 Mar '06

Greg Buchholz wrote: > Is it possible to make a typeclass like Functor, that has a function > (say "f_map"), which would work for the infinite hierarchy of types: > ([],[[]],[[[]]],...)? You do understand that this requires overlapping instances? Because the type [[Bool]] is still a list. In general, an instance that matches on the type [[a]] will also match [[[a]]], etc. That's where the IsFunction-like trick comes in handy. Please note that the overlapping instances are only needed for the implementation of the IsCollection predicate. The typeclass for the deep Funct needs no overlapping instances. The code below is more general that required. It also generic: it works for any Functor and any combination of Functors. It performs fmap over arbitrarily deep `collections': lists of maybes of maps of IOs, etc. -- arbitrarily nested fmappable things. test3 = f_map not (Just [Just True, Nothing]) test4 = f_map not (print "here" >> return (Just (Just [Just [True], Nothing]))) >>= print > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > {-# OPTIONS -fallow-overlapping-instances #-} > > module FMAP where > > data Atom > > -- Check if a type is a collection type. This is the only typeclass that > -- needs overlapping instances > class IsCollection t coll | t -> coll > instance IsCollection (m a) (m ()) > instance TypeCast Atom coll => IsCollection t coll > > -- our common working horse > class TypeCast a b | a -> b, b->a where typeCast :: a -> b > class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b > class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b > instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x > instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' > instance TypeCast'' () a a where typeCast'' _ x = x > > -- The desired deep functor. Needs no overlapping instances > class Funct a b c1 c2 | c1 -> a, c1 b -> c2 where > f_map :: (a -> b) -> c1 -> c2 > > instance (IsCollection c1 coll, Funct' coll a b c1 c2) > => Funct a b c1 c2 where > f_map = f_map' (undefined::coll) > > class Funct' coll a b c1 c2 | coll c1 -> a, coll c1 b -> c2 where > f_map' :: coll -> (a -> b) -> c1 -> c2 > > instance Funct' Atom a b a b where > f_map' _ = id > > instance (Functor m, Funct a b c d) => Funct' (m ()) a b (m c) (m d) where > f_map' _ = fmap . f_map > > > test1 = f_map (+1) [[[1::Int,2,3]]] > test2 = f_map not [[True], [False]] > test3 = f_map not (Just [Just True, Nothing]) > test4 = f_map not (print "here" >> > return (Just (Just [Just [True], Nothing]))) > >>= print

3 2