- Haskell-Cafe - Haskell.org

typeOf for polymorphic value
by oleg＠okmij.org 27 Mar '09

27 Mar '09

> Does anyone know of a trick to accomplish `typeOf id'? > Using something else than TypeRep as the representation, of course. Yes. The analysis of polymorphic types has been used in the inverse type-checker http://okmij.org/ftp/Haskell/types.html#de-typechecker The enclosed code computes TypeRep of polymorphic values. The code returns real TypeRep. Here are a few examples: tt2 = mytypof not -- Bool -> Bool tt3 = mytypof [True] -- [Bool] tt4 = mytypof id -- any1 -> any1 tt5 = mytypof [] -- [any1] tt6 = mytypof const -- any1 -> any2 -> any1 tt7 = mytypof Just -- any1 -> Maybe any1 tt8 = mytypof map -- (any1 -> any2) -> [any1] -> [any2] tt9 = mytypof maybe -- any1 -> (any2 -> any1) -> Maybe any2 -> any1 The code was tested on GHC 6.8.2. I don't have access to any computer with GHC 6.10, so I can't say how it works with that version of GHC. {-# LANGUAGE ScopedTypeVariables, EmptyDataDecls #-} {-# LANGUAGE FlexibleInstances, FlexibleContexts #-} {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE OverlappingInstances #-} {-# LANGUAGE IncoherentInstances #-} module Typeof where import Data.Typeable -- tests tt1 = mytypof True -- Bool tt2 = mytypof not -- Bool -> Bool tt3 = mytypof [True] -- [Bool] tt4 = mytypof id -- any1 -> any1 tt5 = mytypof [] -- [any1] tt6 = mytypof const -- any1 -> any2 -> any1 tt7 = mytypof Just -- any1 -> Maybe any1 tt8 = mytypof map -- (any1 -> any2) -> [any1] -> [any2] tt9 = mytypof maybe -- any1 -> (any2 -> any1) -> Maybe any2 -> any1 class MyTypeable a where mytypof :: a -> TypeRep -- Gamma is the sequence of type varaibles. It is used to assign -- different indices to different type variables instance (Analyze a result, MyTypeable' HNil gout result) => MyTypeable a where mytypof a = fst $ mytypof' HNil (analyze a) class MyTypeable' gin gout classification | gin classification -> gout where mytypof' :: gin -> classification -> (TypeRep,gout) instance Typeable a => MyTypeable' gin gin (TAtomic a) where mytypof' gin _ = (typeOf (undefined::a), gin) instance Typeable a => MyTypeable' gin gin (TAtomic1 a) where mytypof' gin _ = (typeOf (undefined::a), gin) instance (MyTypeable' gin g a, MyTypeable' g gout b) => MyTypeable' gin gout (TFunction a b) where mytypof' gin _ = let (tr1,g) = mytypof' gin (undefined::a) (tr2,gout) = mytypof' g (undefined::b) in (mkFunTy tr1 tr2,gout) instance (MyTypeable' gin g c, MyTypeable' g gout a) => MyTypeable' gin gout (TConstructed c a) where mytypof' gin _ = let (tr1,g) = mytypof' gin (undefined::c) (tr2,gout) = mytypof' g (undefined::a) in (mkTyConApp (typeRepTyCon tr1) [tr2],gout) instance (HIndex a gin n, MyTypeable'' n gin gout (TVariable a)) => MyTypeable' gin gout (TVariable a) where mytypof' = mytypof'' (undefined::n) class MyTypeable'' n gin gout classification | n gin classification ->gout where mytypof'' :: n -> gin -> classification -> (TypeRep,gout) instance HLen gin n1 => MyTypeable'' Z gin (HCons a gin) (TVariable a) where mytypof'' _ gin _ = (mkany (undefined::S n1), HCons (undefined::a) gin) instance Nat n => MyTypeable'' (S n) gin gin (TVariable a) where mytypof'' _ gin _ = (mkany (undefined::S n), gin) mkany :: Nat n => n -> TypeRep mkany n = mkTyConApp (mkTyCon ts) [] where ts = "any" ++ show (nat n) -- Lookup the index of an item x in the list l -- The index is 1-based. If not found, return 0 class Nat n => HIndex x l n | x l -> n instance HIndex x HNil Z instance (Nat n, TypeEq x a f, HIndex' f x (HCons a l) n) => HIndex x (HCons a l) n class HIndex' f x l n | f x l -> n instance HLen l n => HIndex' HTrue x l n instance HIndex x l n => HIndex' HFalse x (HCons a l) n -- Length of a list class Nat n => HLen l n | l -> n instance HLen HNil Z instance HLen l n => HLen (HCons a l) (S n) -- Analyze a type -- Result of the type analysis data TAtomic a data TVariable a data TFunction a b data TConstructed c a -- only one level: kind * -> * data TAtomic1 a data TVariable1 a data Level1 a data W a = W a -- We can have more levels, cf Typeable2, etc. class Analyze a b | a -> b analyze:: Analyze a b => a -> b analyze = undefined instance TypeCast f (TAtomic Int) => Analyze Int f instance TypeCast f (TAtomic Bool) => Analyze Bool f instance TypeCast f (TAtomic Char) => Analyze Char f instance TypeCast f (TAtomic Int) => Analyze (W Int) f instance TypeCast f (TAtomic Bool) => Analyze (W Bool) f instance TypeCast f (TAtomic Char) => Analyze (W Char) f instance (Analyze (c x) rx, Analyze (d y) ry, TypeCast f (TFunction rx ry)) => Analyze (c x->d y) f instance (Analyze (W x) rx, Analyze (d y) ry, TypeCast f (TFunction rx ry)) => Analyze (x->d y) f instance (Analyze (c x) rx, Analyze (W y) ry, TypeCast f (TFunction rx ry)) => Analyze (c x->y) f instance (Analyze (W x) rx, Analyze (W y) ry, TypeCast f (TFunction rx ry)) => Analyze (x->y) f instance (Analyze (W x) rx, Analyze (W y) ry, TypeCast f (TFunction rx ry)) => Analyze (W (x->y)) f instance (Analyze (Level1 (c ())) rc, Analyze (W x) rx, TypeCast f (TConstructed rc rx)) => Analyze (c x) f instance TypeCast f (TAtomic1 ([] ())) => Analyze (Level1 ([] ())) f instance TypeCast f (TAtomic1 (Maybe ())) => Analyze (Level1 (Maybe ())) f instance TypeCast f (TVariable1 (c ())) => Analyze (Level1 (c ())) f -- the most general instance instance TypeCast f (TVariable a) => Analyze (W a) f -- instance TypeCast f (TVariable a) => Analyze a f -- the most general instance {- ta1 = analyze True -- ta1 :: TAtomic Bool ta2 = analyze not -- ta2 :: TFunction (TAtomic Bool) (TAtomic Bool) ta3 = analyze [True] -- ta3 :: TConstructed (TAtomic1 [()]) (TAtomic Bool) ta4 = analyze id -- ta4 :: TFunction (TVariable GHC.Prim.Any) (TVariable GHC.Prim.Any) ta5 = analyze [] -- ta5 :: TConstructed (TAtomic1 [()]) (TVariable GHC.Prim.Any) ta6 = analyze const -- ta6 :: TFunction -- (TVariable GHC.Prim.Any) -- (TFunction (TVariable GHC.Prim.Any) (TVariable GHC.Prim.Any)) -} -- Standard HList stuff data Z data S a class Nat a where nat :: a -> Int instance Nat Z where nat _ = 0 instance Nat a => Nat (S a) where nat _ = succ (nat (undefined::a)) data HTrue data HFalse instance Show HTrue where show _ = "HTrue" instance Show HFalse where show _ = "HFalse" data HNil = HNil deriving Show data HCons a b = HCons a b deriving Show -- literally lifted from the HList library 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 class TypeEq' () x y b => TypeEq x y b | x y -> b where type'eq :: x -> y -> b type'eq _ _ = undefined::b class TypeEq' q x y b | q x y -> b class TypeEq'' q x y b | q x y -> b instance TypeEq' () x y b => TypeEq x y b instance TypeCast b HTrue => TypeEq' () x x b instance TypeEq'' q x y b => TypeEq' q x y b instance TypeEq'' () x y HFalse

2 1

typeOf for polymorphic value
by Lennart Augustsson 27 Mar '09

27 Mar '09

Using Data.Typeable.typeOf we can get a representation of the the type of a monomorphic value, for instance Prelude Data.Typeable> typeOf not Bool -> Bool But if we try using it on a polymorphic value it fails Prelude Data.Typeable> typeOf id <interactive>:1:0: Ambiguous type variable `a' in the constraint: `Typeable a' arising from a use of `typeOf' at <interactive>:1:0-8 Probable fix: add a type signature that fixes these type variable(s) And understandably so. Does anyone know of a trick to accomplish `typeOf id'? Using something else than TypeRep as the representation, of course. Any tricks and existing language extensions are welcome. (As ghc moves towards first class polymorphic values this question gets more interesting.) -- Lennart

2 1

Re: [Haskell-cafe] Grouping - Map / Reduce
by Peter Verswyvelen 27 Mar '09

27 Mar '09

Well, this approach has the problem that the running sum of key k blocks until a new value for that k arrives in the input stream. If you wanted to know the sum of the values of each key after you got nelements in the input stream, we could change the valuesWithKey inner function into: runningSumsOfValuesPerKey :: (Eq k, Num v) => [k] -> [(k, v)] -> [[v]] runningSumsOfValuesPerKey allPossibleKeys = runningSums . allValuesPerKey where runningSums = map (scanl (+) 0) allValuesPerKey pairs = [ valuesWithKey key pairs | key <- allPossibleKeys ] valuesWithKey key = map (\(k,v) -> if k==key then v else 0) then map (!!n) on the result of runningSumsOfValuesPerKey gives you the sum after n elements arrived. I think if you now generalize this so you don't use 0 but mempty, mconcat and other Monoid methods, that you might get something like Luke's trie solution, not sure, Luke is a fair bit smarter than I am :-) But this code is very inefficient I'm afraid, I guess the blueprint stuff that was posted really builds a map incrementally, but I don't understand that yet. Ik spreek Nederlands ja ('t is te zeggen, "Antwerps"). Yes I'm still learning Haskell, but I think with Haskell this is a never ending process, since there's soo much stuff to discover and the language evolves (which makes it both exciting and frustrating, but that's the dilemma of knowledge anyway, the more you know the better you realize the vast amount of knowledge that you don't know yet :-) On Fri, Mar 27, 2009 at 12:53 AM, Guenther Schmidt <gue.schmidt(a)web.de>wrote: > Dear Peter, > > wow, thanks, this is a very ... interesting ... approach, I hadn't thought > about that yet ;) > > Ben je nederlands? > > In case you'd be interested to share the "road to Haskell" experience with > another newbie just ask. > > Günther > > Peter Verswyvelen schrieb: > > I'm also learning Haskell so the solution below might be (1) inefficient >> and (2) incorrect, but hey, let's give it a try :-) >> >> For simplicity, in the testing code, I assume an infinite list of >> key/value pairs where they keys are of type Char between 'a' and 'z' and the >> values are Integers (the code also seems to work for keys with just a lower >> bound but no upper bound) >> I think the code speaks for itself >> >> import System.Random >> runningSumsOfValuesPerKey :: (Eq k, Num v) => [k] -> [(k, v)] -> [[v]] >> runningSumsOfValuesPerKey allPossibleKeys = runningSums . allValuesPerKey >> where >> runningSums = map (scanl (+) 0) >> allValuesPerKey pairs = [ valuesWithKey key pairs | key <- >> allPossibleKeys ] >> valuesWithKey key = map snd . filter ((==key) . fst) >> -- Testing >> randomPairs :: [(Char, Integer)] >> randomPairs = zip keys values >> where >> keys = randomRs ('a','z') rnd1 >> values = randomRs (0,9) rnd2 >> (rnd1,rnd2) = split (mkStdGen 0) >> test = map (take 10) [rs `atKey` 'c', rs `atKey` 'z'] >> where >> rs = runningSumsOfValuesPerKey ['a'..] randomPairs >> xs `atKey` k = xs !! (fromEnum k - fromEnum 'a') >> >> >> >> > >

2 1

ANN: FallingBlocks 0.1
by Ben Sanders 27 Mar '09

27 Mar '09

Hello, I just uploaded fallingblocks to Hackage. It is another Tetris clone, but it uses SDL, and I thought there could be more SDL examples. Any and all comments and suggestions will be extremely appreciated! There is a darcs repo at http://patch-tag.com/publicrepos/fallingblocks Cheers! -Ben

2 1

Re: about Haskell code written to be "too smart"
by John Lato 27 Mar '09

27 Mar '09

> From: wren ng thornton <wren(a)freegeek.org> > Dan Weston wrote: >> So to be clear with the terminology: >> >> inductive = good consumer? >> coinductive = good producer? >> >> So fusion should be possible (automatically? or do I need a GHC rule?) with >> inductive . coinductive >> >> Or have I bungled it? > > Not quite. Induction means starting from base cases and building things > upwards from those. Coinduction is the dual and can be thought of as > starting from the ceiling and building your way downwards (until you hit > the base cases, or possibly forever). > ( quite a lot of text trimmed for brevity) Wren, thank you for contributing this post. Coming from the point of view of someone who doesn't grok it all yet, this is the best commentary I've read on deforestation/fusion, and in fact is helpful for category theory newbies as well (at least I found it so). It really should go on a wiki somewhere. John Lato

2 1

Grouping - Map / Reduce
by Gü?nther Schmidt 26 Mar '09

26 Mar '09

Hi, let say I got an unordered lazy list of key/value pairs like [('a', 99), ('x', 42), ('a', 33) ... ] and I need to sum up all the values with the same keys. So far I wrote a naive implementation, using Data.Map, foldl and insertWith. The result of this grouping operation, which is effectively another list of key/value pairs, just sums this time, needs to be further processed. The building of this map is of course a bottleneck, the successive processing needs to wait until the entire list is eventually consumed the Map is built and flattened again. Is there another way of doing this, something more "streaming architecture" like? Is Googles "Map - Reduce" related to this? Günther

8 10

an OS-independent executeFile??
by Vasili I. Galchin 26 Mar '09

26 Mar '09

Hello, I have been looking through Hackage and using Hoogle to "fork and execute" a program in an OS-independent way, i.e. neutral from POSIX and Win32 APIs. Does such a library function exist? Regards, Vasili

2 4

Language.Haskell.Parser question
by Vasyl Pasternak 26 Mar '09

26 Mar '09

Hi, I want to parse haskell file to find all calls to function 'foo' and gathers a create a list of all argumets, which passed to it. E.g. from the following code: f1 = foo 5 f2 = foo 8 f3 = foo 9 I want to extract a list [5, 8, 9] (suppouse function takes only one argument) The most obvious way is to use Language.Haskell for this task. The parser works pretty good, but its output data type is terrible. As I understand, I need to extract all objects that looks like HsApp (HsVar (UnQual (HsIdent "foo"))) .... The question is, is there a method to do it quickly or I have to process each object of different type separately ? Maybe it is a work for a template Haskell ? Thanks. -- Best regards, Vasyl Pasternak

4 7

Compile OpenGL for jhc
by Csaba Hruska 26 Mar '09

26 Mar '09

Hi! As OpenGL haskell binding depends only on base, it would be great to compile it with jhc. I've tried to do that, but I had some problems with preprocessor directives. It would be also great to add jhc support for OpenGL bindings build scripts. Or, it would be better to add jhc support for cabal-install. :) Is there anyone who has any idea any of this things? (for soulution)

2 3

ANN: io-capture-0.2 capturing std(out|err) in IO action
by Yusaku Hashimoto 26 Mar '09

26 Mar '09

Hi, I announce the release of io-capture package of version 0.2 io-capture is a Library to capturing stdout and stderr in IO action. It exports a function named `capture', It takes an IO and an String, the action to run and the given whole stdin, and returns whole stdout and stderr in the action as String. For example: ghci> :m +System.IO.Capture ghci> :m +System.IO ghci> capture (getLine >>= putStr >> getLine >>= hPutStr stderr) "foo \nbar\n" ("foo","bar") io-capture is available on hackage, repository is on patch-tag. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/io- capture-0.2 http://patch-tag.com/repo/io-capture/browse It behaves almost fine, but It's still experimental, I know some trouble about when given lazy reading action such as getContents. And there may be unknown bugs. If you find it, feel free to report it and any feedbacks are welcome. Thanks for reading, Yusaku Hashimoto

1 0