Re: [Haskell-cafe] A wish for relaxed layout syntax
Andrzej Jaworski wrote: Good direction. Perhaps you can also figure out how to replace the disturbing $ operator? Something out of Unicode? ≬⊳⌁⋆☕⚡‣‸‡⁏•△▴◆◇◊◬◢◮♘♣♲♪◖▻▿轢 Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A wish for relaxed layout syntax
David House wrote: I see this a lot. My personal preference is: mylist = [ foo, bar, baz, qux, quux, foo, bar, baz, qux ] Or, mylist = [foo, bar , baz, qux, quux, foo, bar, baz , qux] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] IO is not a monad (and seq, and in general _|_)
Brandon S. Allbery KF8NH wrote: That's not quite what I was trying to say. (p^~p)-q is equivalent to _|_ in the sense that once you derive/compute (respectively) it, the world in which it exists breaks. (I don't think formal logic can have a Haskell-like _|_, but deriving (p^~p)-q is close to it in effect.) Here's a couple of papers you might like... Fast and Loose Reasoning is Morally Correct http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/fast+loose.pdf Precise Reasoning About Non-strict Functional Programs How to Chase Bottoms, and How to Ignore Them http://www.cs.chalmers.se/~nad/publications/danielsson-lic.pdf Total Functional Programming http://www.jucs.org/jucs_10_7/total_functional_programming/jucs_10_07_0751_0768_turner.pdf Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mapTuple (intersection types?)
Udo Stenzel wrote: Marco T?lio Gontijo e Silva wrote: is there a way to defined something as a map to use in tuples? I tried this: mapTuple f (a, b) = (f a, f b) But the type inferred to it is not as generic as I wanted: mapTuple :: (t - t1) - (t, t) - (t1, t1) What you seem to want to do is impossible. Just want type would you want to assign to mapTuple? I bet you can't even express that in natural language, no wonder it's impossible in Haskell. Maybe some of the type experts could pipe up, but couldn't you express that as an intersection type? mapTuple :: ((a - b) ^ (c - d)) - (a,c) - (b,d) http://www.cs.cmu.edu/~rwh/theses/pierce.pdf Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why can't you surround (+) in backticks and have it be infix?
tphyahoo wrote:
Issues: In Haskell, any function or constructor can be enclosed in backticks
and then used as an infix operator.
from http://www-users.cs.york.ac.uk/~mfn/hacle/issues/node2.html
But this seems to be contradicted by...
from #haskell
-- 09:19 tphyahoo let func = (+) in 1 `func` 2
-- 09:19 lambdabot 3
-- 09:20 tphyahoo but ..
-- 09:20 tphyahoo 1 `(+)` 2
-- 09:20 tphyahoo 1 `(+)` 2
-- 09:20 lambdabot Parse error
(+) is a function, is it not?
Where's the rub?
The thing inside the backticks has to be a syntatic name, not an
expression. The grammar from the Haskell Report
( http://www.haskell.org/onlinereport/syntax-iso.html )...
varid -(small {small | large | digit | ' })reservedid
conid -large {small | large | digit | ' }
varop -varsym | `varid ` (variable operator)
qvarop -qvarsym | `qvarid ` (qualified variable operator)
conop -consym | `conid ` (constructor operator)
qconop -gconsym | `qconid ` (qualified constructor operator)
...I've also thought it would be nice to be able to say things like...
(foo `liftM2 (,)` bar)
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Seeking advice on a style question
Steve Schafer wrote: Here's the essence of the problem. If I have this: process1 x y = let u = foo x y; v = bar u; w = baz v in w I can easily rewrite it in point-free style: process1 = baz . bar . foo Not unless you have a much fancier version of function composition, like... http://okmij.org/ftp/Haskell/types.html#polyvar-comp But if I have this: process2 x y = let u = foo x y; v = bar u; w = baz v u in w then I can't avoid naming and using an intermediate variable. And that annoys me. The u in process2 is of no more value to me (pardon the pun) as the one in process1, but I am forced to use it simply because the data flow is no longer strictly linear. The reason I brought up monads as a possible means of managing this problem is that the State, Reader and Writer monads already handle certain specific shapes of nonlinear data flow, which suggested to me that maybe there was a monadic approach to managing nonlinear data flow in a more general way. Of course, if there is a non-monadic, purely functional way to do it, that would be even better, but I've never seen such a thing (short of doing lots of tupling and un-tupling). -- Use combinators which automate the tupling/un-tupling. -- See also, the Joy language... -- http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html main = process2 test process2 = baz . bar . dup . foo foo = mul . (push 2) . mul bar = rep . swap . (push 'A') baz = add . len test = (2,(3,()))::(Int,(Int,())) dup (a,b) = (a,(a,b)) swap (a,(b,c)) = (b,(a,c)) push a b = (a,b) lift1 f (a,b) = (f a,b) lift2 f (a,(b,c)) = (f a b,c) len = lift1 length add = lift2 (+) mul = lift2 (*) rep = lift2 replicate ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Seeking advice on a style question
Conal Elliott wrote: Warning: I haven't tried to type-check and may have made a clerical error. Since questionCategories isn't used, use fst eliminate another let. Then, for my personal preference, and just to mix things up, switch to where style: process item mediaKind mediaSize language = flip combineRows sequenceLayouts $ paginate item mediaKind mediaSize pagemaster $ groupBands $ resolveCrossReferences $ bands where (bands,sequenceLayouts) = buildLayout mediaKind language $ coalesceNAQuestions $ fst $ numberQuestions pagemaster $ stripUndisplayedQuestions mediaKind $ appendEndQuestions item (loadPagemaster item mediaKind mediaSize) $ coalesceParentedQuestions $ validateQuestionContent $ loadQuestions item And just for the heck of it, trading parenthesis and layout for dollar signs... process item mediaKind mediaSize language = combineRows (paginate item mediaKind mediaSize pagemaster (groupBands (resolveCrossReferences bands))) sequenceLayouts where (bands,sequenceLayouts) = buildLayout mediaKind language (coalesceNAQuestions (fst (numberQuestions pagemaster (stripUndisplayedQuestions mediaKind (appendEndQuestions item (loadPagemaster item mediaKind mediaSize) (coalesceParentedQuestions (validateQuestionContent (loadQuestions item ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multi parameter type classes for NP problems
Joshua Ball wrote: Here is how I am trying to solve the problem, using multi-parameter type classes. class NPProblem inst cert where validates :: cert - inst - Bool certificates :: inst - [cert] decide :: inst - Bool decide i = any (\x - x `validates` i) $ certificates i Unfortunately, ghc throws the following type error: NPProblem.hs:5:45 Could not deduce (NPProblem inst a) from the context (NPProblem inst cert) arising from use of `certificates' at NPProblem.hs:5:45-58 Possible fix: add (NPProblem inst a) to the class or instance method `decide' In the second argument of `($)', namely `certificates i' In the expression: (any (\ x - x `validates` i)) $ (certificates i) In the definition of `decide': decide i = (any (\ x - x `validates` i)) $ (certificates i) Maybe something like?... class NPProblem inst cert where validates :: cert - inst - Bool certificates :: inst - [cert] decide :: inst - Bool decide i = any (\x - x `validates` i) $ (certificates i :: [cert]) ...or a functional dependency of some sort... class NPProblem inst cert | inst - cert where ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type keeping rounding, typeable (and a difficulty)
isto wrote: ] isto wrote: ] ] let t = show (typeOf a) ] ] in case t of ] ] Double - roundDDec d a ] ] Complex Double - roundCDec d a ] ] I'll guess the reason it didn't compile was different ] types at case branches (am I wrong?) Correct. ] Anyhow, do you know that is it possible to choose the return type ] somehow in the spirit above? Maybe you want something like... roundDec d (Left a) = Left (roundDDec d a) roundDec d (Right a) = Right (roundCDec d a) roundCDec :: (RealFloat a) = Int - Complex a - Complex a roundCDec d (c :+ b) = (roundDDec d c :+ roundDDec d b) roundDDec :: (RealFloat a) = Int - a - a roundDDec d a = a -- or somegthing Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type keeping rounding, typeable (and a difficulty)
isto wrote: ] I've been trying to compile the following function ] (rounding to a desired degree): ] ] roundDec :: (Num a, Typeable a) = Int - a - a ] roundDec d a = ] let t = show (typeOf a) ] in case t of ] Double - roundDDec d a ] Complex Double - roundCDec d a ] otherwise - a -- or something ] ] The two other functions are ] ] roundCDec :: (RealFloat a) = Int - Complex a - Complex a ] roundCDec d (c :+ b) = (roundDDec d c :+ roundDDec d b) ] and ] roundDDec :: (RealFloat a) = Int - a - a ] roundDDec d a = a -- or somegthing Maybe you want type classes instead? import Complex class Round a where roundD :: Int - a - a instance Round Double where roundD d a = a instance (Round a, RealFloat a) = Round (Complex a) where roundD d (c :+ b) = (roundD d c :+ roundD d b) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (twice head) (twice tail)
Over on comp.lang.functional ( http://xrl.us/s6kv ), Toby Kelsey is wondering about writing a function twice that applies a function to an argument two times... twice' :: (a - a) - a - a twice' f x = f (f x) ...that works for things like twice succ 0 and twice tail [1,2,3], but the type signature means you can't try something like twice head [[1]]. You can get the twice head case to work with a function like... twice'' :: (forall a. (m a) - a) - (m (m b)) - b twice'' f x = f (f x) ...and if you want something like twice (flip (:) []), you'd use... twice''' :: (forall a. a - (m a)) - b - (m (m b)) twice''' f x = f (f x) ...it seems like those type signatures have at least a passing resemblance, so I was wondering if you could use type classes to combine these functions. I tried something like... class Twice a b c | a b - c where twice :: a - b - c instance Twice (a-a) a a where twice f x = f (f x) instance Twice (forall a. (m a) - a) (m (m b)) b where twice f x = f (f x) ...but with ghc-6.6 it chokes with... Illegal polymorphic or qualified type: forall a. m a - a In the instance declaration for `Twice (forall a. (m a) - a) (m (m b)) b' ...I can't say I'm surprised, but I was wondering if anyone else has thoughts on how this limitation might be worked around. Curious, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: An example of dependent types [was: Simple GADT parser for the eval example]
[EMAIL PROTECTED] wrote: Greg Buchholz has posed an interesting problem of writing a typechecker. Given untyped terms of the form ...snip... We show the solution that uses no GADTs and no representation types. We retain however the eval function in the previous message that uses GADT. Our solution uses type classes. It seems to some the type-checking rules stated as instances of the TypeCheck class take a particular natural form. ...snip... rather than the original terms Exp. The conversion is straightforward, via Template Haskell: type F = Q TH.Exp parse :: Expr - F parse (ELit x) = [e| FLit $(litE . integerL . fromIntegral $ x) |] parse (EInc x) = [e| FInc $(parse x) |] parse (EIsZ x) = [e| FIsZ $(parse x) |] t1' = $(parse . read $ e1) t2' = $(parse . read $ e2) *G :t t1' t1' :: FIf FLit FLit FLit *G :t t2' t2' :: FIf (FIsZ FLit) (FInc FLit) (FFst (FPair FLit FLit)) Nice. But using TH means we have to know everthing about the strings we want to evaluate at compile time right? So you can't do something like... main = do l - getLine print $ (eval.typecheck) ($(parse . read $ l)) ...right? (Even if you can get around GHC complaining about a 'stage restriction'). Whereas, it would be possible with with the my_read and other versions. Anyway, as long as we're going down that route, we might as well get rid of the GADTs and go for a pure type class version of eval... http://lambda-the-ultimate.org/node/1787 ...(great minds think alike, right? ;-) I guess I should have mentioned that thread in my first message. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A type class puzzle
Yitzchak Gale wrote: Tomasz Zielonka wrote: If you insist that each index should be given as a separate function argument, it may be possible to achieve it using the tricks that allow to write the variadic composition operator. I am not familiar with that. Do you have a reference? Is that the best way to do it? (Is that a way to do it at all?) You might find these articles somewhat related... Functions with the variable number of (variously typed) arguments http://okmij.org/ftp/Haskell/types.html#polyvar-fn Deepest functor [was: fmap for lists of lists of lists of ...] http://okmij.org/ftp/Haskell/deepest-functor.lhs ...That first article is the strangest. I couldn't reconcile the fact that if our type signature specifies two arguments, we can pattern match on three arguments in the function definition. Compare the number of arguments in the first and second instances... class BuildList a r | r- a where build' :: [a] - a - r instance BuildList a [a] where build' l x = reverse$ x:l instance BuildList a r = BuildList a (a-r) where build' l x y = build'(x:l) y ...if you try something like... foo :: [a] - a - r foo l x y = undefined ...you'll get an error message like... The equation(s) for `foo' have three arguments, but its type `[a] - a - r' has only two YMMV, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] A type class puzzle
Rearranging... Nicolas Frisby wrote: On 10/31/06, Greg Buchholz [EMAIL PROTECTED] wrote: ...That first article is the strangest. I couldn't reconcile the fact that if our type signature specifies two arguments, we can pattern match on three arguments in the function definition. Compare the number of arguments in the first and second instances... See Connor McBride's Faking It: Simulating Dependent Types in Haskell http://citeseer.ist.psu.edu/mcbride01faking.html It might help; your example makes me think of the nthFirst function. If it's different, I'md wager the polyvariadic stuff and nthFirst can be reconciled on some level. Does that explain how, why, or when you can use more arguments than you are allowed to use? Or is it just another example of using more arguments than you are allowed to use? Is this a Haskell 98 thing, or is it related to MPTCs, or fun deps, or something else? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A type class puzzle
Arie Peterson wrote: ] I'm not sure I'm getting your point, but this is just because in the ] second instance, the second parameter of BuildList is 'a - r', so the ] specific type of 'build\'' is '[a] - a - (a - r)' which is just '[a] - ] a - a - r' (currying at work). I guess it just looks really strange to my eyes. For example, foo and bar are legal, but baz isn't. That's what I was thinking of the situation, but I guess the type classes iron out the differences. foo :: Int - Int - Int - Int foo 0 = (+) bar :: Int - Int - Int - Int bar 1 x = succ baz :: Int - Int - Int - Int baz 0 = (+) baz 1 x = succ Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple GADT parser for the eval example
Thanks to everyone who replied (especially Dimitrios Vytiniotis and
Joost Visser). I now know the standard way to write the GADT parser.
But I'm still curious if anyone has comments pertaining to the version
using type classes. It seems so close to doing what we want, and it is
pretty straightforward to implement. The best way I can think to
describe it would be to say it uses the type system to find what it
should parse next, and dies of a pattern match failure if something
unexpected shows up, instead of checking to see if we can assemble a
type safe tree from pre-parsed parts (does that make any sense?).
I'm curious if there could be a small change to the type system to
make the fully general my_read possible, or if it suffers from an
incurable defect.
Thanks,
Greg Buchholz
{-# OPTIONS -fglasgow-exts #-}
main = print test
test :: Int
test = eval.my_read.read $
(EIf (EIsZ (ELit 0)) ++
(EInc (ELit 1)) ++
(EFst (EPair (ELit 42)++
(ELit 43
class MyRead a where
my_read :: Expr - Term a
instance MyRead Int where
my_read (ELit a)= Lit a
my_read (EInc a)= Inc (my_read a)
my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e)
my_read (EFst a)= Fst (my_read a :: Term (Int,Int))
my_read (ESnd a)= Snd (my_read a :: Term (Int,Int))
instance MyRead Bool where
my_read (EIsZ a)= IsZ (my_read a)
my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e)
my_read (EFst a)= Fst (my_read a :: Term (Bool,Bool))
my_read (ESnd a)= Snd (my_read a :: Term (Bool,Bool))
instance (MyRead a, MyRead x) = MyRead (a,x) where
my_read (EPair a b) = Pair (my_read a) (my_read b)
my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e)
data Expr = ELit Int
| EInc Expr
| EIsZ Expr
| EPair Expr Expr
| EIf Expr Expr Expr
| EFst Expr
| ESnd Expr
deriving (Read,Show)
data Term a where
Lit :: Int - Term Int
Inc :: Term Int - Term Int
IsZ :: Term Int - Term Bool
If :: Term Bool - Term a - Term a - Term a
Pair :: Term a - Term b - Term (a,b)
Fst :: Term (a,b) - Term a
Snd :: Term (a,b) - Term b
eval :: Term a - a
eval (Lit i)= i
eval (Inc t)= eval t + 1
eval (IsZ t)= eval t == 0
eval (If b t e) = if eval b then eval t else eval e
eval (Pair a b) = (eval a, eval b)
eval (Fst t)= fst (eval t)
eval (Snd t)= snd (eval t)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Simple GADT parser for the eval example
I'm trying to create a simple parser for the GADT evaluator from the wobbly types paper, and I need a little help. Here's the GADT and the evaluator... data Term a where Lit :: Int - Term Int Inc :: Term Int - Term Int IsZ :: Term Int - Term Bool If :: Term Bool - Term a - Term a - Term a Pair :: Term a - Term b - Term (a,b) Fst :: Term (a,b) - Term a Snd :: Term (a,b) - Term b eval :: Term a - a eval (Lit i)= i eval (Inc t)= eval t + 1 eval (IsZ t)= eval t == 0 eval (If b t e) = if eval b then eval t else eval e eval (Pair a b) = (eval a, eval b) eval (Fst t)= fst (eval t) eval (Snd t)= snd (eval t) ...and instead of writing my own read instance, I thought I'd take a shortcut and just try converting a regular data type to our generalized one... data Expr = ELit Int | EInc Expr | EIsZ Expr | EPair Expr Expr | EIf Expr Expr Expr | EFst Expr | ESnd Expr deriving (Read,Show) my_read' :: Expr - Term a my_read' (ELit a) = Lit a my_read' (EInc a) = Inc (my_read' a) my_read' (EIsZ a) = IsZ (my_read' a) my_read' (EPair a b) = Pair (my_read' a) (my_read' b) my_read' (EIf p t e) = If (my_read' p) (my_read' t) (my_read' e) my_read' (EFst a) = Fst (my_read' a) my_read' (ESnd a) = Snd (my_read' a) ...That looks nice and simple, but it doesn't type check. GHCi-6.6 complains... Couldn't match expected type `a' (a rigid variable) against inferred type `Int' `a' is bound by the type signature for `my_read' at eval_gadt_wobbly.hs:45:24 Expected type: Term a Inferred type: Term Int In the expression: Lit a In the definition of `my_read': my_read (ELit a) = Lit a ...No surprise there, since there is no way to fail in the event of a maltyped Expr. The next thing to try is a type class solution... class MyRead a where my_read :: Expr - Term a instance MyRead Int where my_read (ELit a) = Lit a my_read (EInc a) = Inc (my_read a) my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) my_read (EFst a) = Fst (my_read a :: MyRead b = Term (Int,b)) --my_read (ESnd a) = Snd (my_read a) instance MyRead Bool where my_read (EIsZ a) = IsZ (my_read a) my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) --my_read (EFst a) = Fst (my_read a) --my_read (ESnd a) = Snd (my_read a) instance (MyRead a, MyRead b) = MyRead (a,b) where my_read (EPair a b) = Pair (my_read a) (my_read b) my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) --my_read (EFst a) = Fst (my_read a) --my_read (ESnd a) = Snd (my_read a) This just about works, except for the definitions for the Fst and Snd constructors. The compiler complains... Ambiguous type variable `b' in the constraint: `MyRead b' arising from use of `my_read' at eval_gadt_wobbly.hs:65:28-36 Probable fix: add a type signature that fixes these type variable(s) ...Of course, that makes perfect sense, since, if we're applying Fst to a term, then we don't care about the other branch of the Pair. You can get it accepted by the type checker by making the types more concrete... my_read (EFst a) = Fst (my_read a :: Term (Int,Int)) ...or... my_read (EFst a) = Fst (my_read a :: Term (Int,Bool)) ...but how does a person fix this to work in the more general case? Or is this even the right way to build a parser for the GADT evaluator example? Notice the repetition needed: the If, Fst, and Snd defintions have to be copied to all three instances. Also, feel free to comment on this example, and the fact that it will evaluate with no problems. static_vs_laziness = eval (my_read (EIf (EIsZ (ELit 0)) (ELit 9) (EIsZ (ELit 42)))::Term Int) Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Rank N type tutorial?
Anyone know of a good source for learning about higher ranked types? I'm not quite sure why this is illegal... foo :: Integer - (forall a. Show a = a) foo 2 = [foo] foo x = x ...while this is just fine... bar :: Integer - (forall a. Show a = a-b) - b bar 2 k = k [bar] bar x k = k x Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rank N type tutorial?
Ben Rudiak-Gould wrote: The way to think about it is that foralls are extra function arguments. Your first example is like foo :: Integer - (a::Type - Show a - a) so a is chosen by the caller, not by you. The second case is like bar :: Integer - (a::Type - Show a - a - b) - b In order for the first case to work as you expect, you'd need the type foo :: Integer - (a::Type, Show a, a) which is traditionally written foo :: Integer - (exists a. Show a = a) I thought exists was spelled forall in Haskell? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] function types as instances of Num
Let's say we've got a little stack language, where you compute
things by transformations of stacks, using compositions of functions
from stacks to stacks (represented here as nested tuples). (See also
Chris Okasaki's Techniques for Embedding Postfix Languages in Haskell
www.eecs.harvard.edu/~nr/ cs252r/archive/chris-okasaki/hw02.ps )
For example, the simple program below calculates the square of 4...
{-# OPTIONS -fglasgow-exts #-}
main = print $ test ()
test = square . (lit 4)
lit :: Integer - a - (Integer,a)
lit val stack= (val, stack)
dup (a, b) = (a, (a, b))
mult (a, (b, c)) = (b*a, c)
square = mult . dup
...now let's say I find that using the function lit to annotation
numeric literals ugly. What I really want is something like...
test' = square . 4
...Seems simple enough, I'll just make an appropriate instance of Num
and I'll be able to use fromInteger...
instance Eq (a - (Integer, a))
instance Show (a - (Integer, a))
instance Num (a - (Integer, a)) where
fromInteger = lit
...but now when I try it, GHC complains...
No instance for (Num (a - (Integer, t)))
arising from the literal `4' at final.hs:15:17
Possible fix:
add an instance declaration for (Num (a - (Integer, t)))
In the second argument of `(.)', namely `4'
In the expression: square . 4
In the definition of `test'': test' = square . 4
...so it seems that (a - (Integer, t)) can't be unified with (a -
(Integer, a)), or somesuch. Any thoughts on how to get this to work?
Thanks,
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function types as instances of Num
Dan Weston wrote: How about: Hmm. I'm probably being dense today, but when I add the following definitions to your program... main = print $ (square . 4) () square (a,b) = (a*a,b) ...I still get the same error... No instance for (Num (() - (t, t1))) arising from the literal `4' at weston.hs:5:25 Possible fix: add an instance declaration for (Num (() - (t, t1))) In the second argument of `(.)', namely `4' In the second argument of `($)', namely `(square . 4) ()' In the expression: print $ ((square . 4) ()) ...maybe you could show me your implementation of main and square to help nudge me in the right direction. (I'm using ghc-6.6) Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: (more) type level functions (type of decreasing list)
[EMAIL PROTECTED] wrote: ] ] One way is to use existentials: ] data Seq1 a = forall b. (Pre a b, Show b) = Cons1 a (Seq1 b) | Nil1 ] ] which perhaps not entirely satisfactory because we have to specify all ] the needed classes in the definition of Seq1. Yes, that seems pretty burdensome, since we can't now create even a simple function like tail, right? Or at least I think existentials are the problem with this... tail1 :: (Pre a b, Show b) = Seq1 a - Seq1 b -- tail1 (Cons1 x xs) = xs tail1 Nil1 = error empty Seq ...ghci reports... Couldn't match expected type `b' (a rigid variable) against inferred type `b1' (a rigid variable) `b' is bound by the type signature for `tail_' at dec2.lhs:30:17 `b1' is bound by the pattern for `Cons1' at dec2.lhs:31:8-17 Expected type: Seq1 b Inferred type: Seq1 b1 In the expression: xs In the definition of `tail1': tail1 (Cons1 x xs) = xs ...and hugs... ERROR dec2.lhs:31 - Existentially quantified variable in inferred type *** Variable : _3 *** From pattern : Cons1 x xs *** Result type : Seq1 _0 - Seq1 _3 ] ] Perhaps a better -- and a more general alternative -- is to use ] type-level programming to its fullest. The following defines a list ] whose elements are constrained to be in the decreasing, increasing, ] or any other (defined in the future) order. This example shows that ] Haskell truly has more kinds than it is commonly acknowledged. snip ] data Cons a b = Cons a b ] data Nil = Nil ...if we build our lists with tuple-like Conses, our types end up being as long as our lists, right? So an infinite list has an infinite type, which seems like it could be problematic to type check. For example, here's an arbitrarly long increasing list... data Seq' a = Cons' a (Seq' (Succ a)) | Nil' deriving Show from :: a - Seq' a from x = Cons' x (from (S x)) inf = from Z ...with some of the usual functions... tail_ :: Seq' a - Seq' (Succ a) tail_ (Cons' x xs) = xs class Take a where take_ :: a - (Seq' b) - (Seq' b) instance Take Zero where take_ Z _ = Nil' instance Take a = Take (Succ a) where take_ (S n) (Cons' x xs) = Cons' x (take_ n xs) take_ _ Nil' = error can't take_ that many class Drop a b c | a b - c where drop_ :: a - Seq' b - Seq' c instance Drop Zero b b where drop_ Z xs = xs instance Drop a (Succ b) c = Drop (Succ a) b c where drop_ (S n) (Cons' x xs) = drop_ n xs drop_ _ Nil' = error can't drop_ that many ...Anyway, for fun, here's a list that alternates between two types in a linearly increasing manner. So you can start out with one Int and then two Strings, then three Ints, four Strings, etc. I don't know if it is going to yeild to a type classless GADT solution yet, but I'll keep thinking about it. data Fancy a b left next = forall c d left' next' lz decleft . (Show c, Show d, Zerop left lz, If lz (Succ next) next next', Pre left decleft, If lz next decleft left', If lz b a c, If lz a b d ) = Cons a (Fancy c d left' next') | Nil fancy :: Fancy Integer String Zero (Succ Zero) fancy = (Cons 1 (Cons a (Cons b (Cons 2 (Cons 3 (Cons 4 (Cons c (Cons d (Cons e (Cons f (Cons 5 (Cons 6 (Cons 7 (Cons 8 (Cons 9 Nil))) instance (Show a, Show b) = Show (Fancy a b c d) where show (Cons x xs) = (Cons ++ (show x) ++ ++ (show xs) ++ ) show Nil = Nil data Succ a = S a deriving Show data Zero = Z deriving Show data TTrue data TFalse class Pre a b | a - b instance Pre (Succ a) a instance Pre Zero Zero class If p t e result | p t e - result instance If TTrue a b a instance If TFalse a b b class Zerop a b | a - b instance Zerop Zero TTrue instance Zerop (Succ a) TFalse ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: type level functions (type of decreasing list)
Stefan Holdermans [EMAIL PROTECTED] wrote: What about the following (tested with GHC 6.6)? and [EMAIL PROTECTED] wrote: One way is to use existentials: snip Perhaps a better -- and a more general alternative -- is to use type-level programming to its fullest. Thanks everyone, those are interesting solutions! Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type level functions (type of decreasing list)
I'm wondering about creating a data structure that has the type of
decreasing numbers. If I want an increasing list, it is easy...
{-# OPTIONS -fglasgow-exts #-}
data Succ a = S a deriving Show
data Zero = Z deriving Show
data Seq' a = Cons' a (Seq' (Succ a)) | Nil' deriving Show
...which can be used like...
zero = Z
one = S zero
two = S one
three = S two
increasing = Cons' zero (Cons' one (Cons' two (Cons' three Nil')))
...on the other hand, if I want the decreasing list, I can try...
class Pre a b | a - b
instance Pre (Succ a) a
instance Pre Zero Zero
data (Pre a b) = Seq a = Cons a (Seq b) | Nil
decreasing = Cons three (Cons two (Cons one Nil))
...but that complains about Not in scope: type variable `b'. Of
course that makes perfect sense, but I'd like to know if there is a
Haskell idiom that I'm missing in order to get this to work.
Thanks,
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type level functions (type of decreasing list)
Spencer Janssen wrote:
] Here's an attempt with GADTs:
]
] \begin{code}
] {-# OPTIONS_GHC -fglasgow-exts #-}
] data Succ a
] data Zero
] data Seq a b where
] Cons :: a - Seq a b - Seq a (Succ b)
] Nil :: Seq a Zero
] \end{code}
]
] Seems to work for me.
Hmm. Maybe I'm missing something. With the program below I get the
following error message (with ghci 6.6)...
Couldn't match expected type `Succ Zero'
against inferred type `Zero'
Expected type: Succ (Succ (Succ Zero))
Inferred type: Succ (Succ Zero)
In the first argument of `Cons', namely `two'
In the second argument of `Cons', namely
`(Cons two (Cons one Nil))'
{-# OPTIONS -fglasgow-exts #-}
data Succ a = S a deriving Show
data Zero = Z deriving Show
zero = Z
one = S zero
two = S one
three = S two
data Seq a b where
Cons :: a - Seq a b - Seq a (Succ b)
Nil :: Seq a Zero
decreasing = Cons three (Cons two (Cons one Nil))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Q Programming Language can do symbolic manipulation -- Haskell?
Casey Hawthorne wrote: The Q Programming Language can do the following: sqr X = X*X ==sqr 5 25 ==sqr (X+1) (X+1)*(X+1) Can Haskell do symbolic manipulation? Typeful symbolic differentiation of compiled functions http://www.haskell.org/pipermail/haskell/2004-November/014939.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Type-Level Naturals Like Prolog?
Jared Warren wrote: Haskell's type checking language is a logical programming language. The canonical logical language is Prolog. Why can't Haskell (with extensions) do type-level Peano naturals in the same fashion? The code would be something like: Also of possible interest, _Fun with Functional Dependencies_... http://www.cs.chalmers.se/~hallgren/Papers/wm01.html This paper illustrates how Haskell's type class system can be used to express computations. Since computations on the type level are performed by the type checker, these computations are static (i.e., performed at compile-time), and, since the type system is decidable, they always terminate. Haskell thus provides a means to express static computations, and has a clear distinction between static and dynamic computations. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lists as instances of a class?
David Roundy wrote: I'm sure I'm missing something lame here, but can someone tell me why we apparently can't declare a list to be an instance of a class in Haskell 98? I think it is a feature of H98 intended to disallow any possibility of overlapping instances. If you have... instance Vec [Double] ...there's nothing from stopping you from also declaring... instance Num a = Vec [a] ...but since Double is a member of Num, which instance should the compiler use? Or is there perhaps some other syntax by which I'd declare this instance? Not by the looks of section 4.3.2 of the Haskell Report (at least by my reading). Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Eager Parser Combinators [was: Functional programming for processing of largeraster images]
Ralf Hinze wrote: Also, in a non-strict language recursive definitions are not limited to function types. Users of parser combinators heavily rely on this feature. Just try to define/use parsing combinators ins a strict language. Anyone care to comment on what goes wrong with parser combinators in an eager language? Is it mainly a space usage problem (where the lazy version might essentially perform a depth-first-search, while the eager version is breadth-first)? Or is there something else I'm missing? As a reference, back when I was trying to understand monads, I ported the parser combinators from the Hutton and Meijer paper to perl... http://sleepingsquirrel.org/monads/parser/monad_parser.txt Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Learning C after Haskell
Chad Scherrer wrote: My question is, as I learn C, are there any particular Haskell concepts I should keep in the back of my mind, or is it better to approach C from scratch? One thing from Haskell I'd try keep in mind is to minimize side effects and keep the scope of side effects as contained and local as possible. So avoid mutating global variables, try not to write to the same file from multiple different subroutines, etc. And if you start getting seg-faults, you'll probably want a tool to help you, since reasoning and debug by printf on pointers can only take you so far in a language like C. http://www.gnu.org/software/libc/manual/html_node/Allocation-Debugging.html http://perens.com/FreeSoftware/ElectricFence/ http://valgrind.org/ Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Inferred type not most general?
I'm curious about a type inference oddity. In the code below, if I leave off the type signature for tmap, both GHC and Hugs infer that tmap has type... tmap :: (b - a, b - a) - Twist b b - Twist a a ...I'm wondering why they couldn't infer the more general... tmap :: (a - b, c - d) - Twist a c - Twist b d data Twist a b = Nil | Cons a (Twist b a) deriving Show x = (Cons foo (Cons 1 (Cons bar (Cons 2 Nil tmap :: (a-b,c-d) - Twist a c - Twist b d tmap _ Nil = Nil tmap (f,g) (Cons x rest) = Cons (f x) (tmap (g,f) rest) Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
Christophe Poucet wrote:
The idea however is that MonoType is going to be used in a recursive
way. For instance:
newtype FMT = FMT MonoType FMT
instance FMT where...
Er, I'll ignore this part.
And this definition will have to reside on recursive definitions. In the
style of how HasVars was instantiated:
instance HasVars a = HasVars (MonoType a) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) $ xs
So for Type
instance Type a = Type (MonoType a) where
...
That's where it becomes rather troublesome.
Yeah, after a certain point of complexity with type classes, it
starts to look like C++ templates. How about something like...
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
import List
type Var = String
type Const = String
data MonoType mt = TyVar Var
| TyConst Const [mt] deriving (Eq, Show)
data PolyType mt = TyPoly [Var] mt deriving (Show)
class Type a b where
toType :: b - a b
fromType :: a b - b
freeVars :: a b - [Var]
occurs :: Var - a b - Bool
data Nil = Nil
instance Type MonoType Nil where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = [???]
instance (Type a b) = Type MonoType (a b) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) $ xs
main = print $ freeVars $
TyConst foo [TyConst bar [Nil],
TyConst baz [Nil],
TyVar quux ]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
Christophe Poucet wrote: I'm not certain but I think this will still fail for exactly the piece that you ignored, which is the crux of the problem. -- You're not looking for this solution, right? import List type Var = String type Const = String data MonoType mt = TyVar Var | TyConst Const [mt] deriving (Eq, Show) data PolyType mt = TyPoly [Var] mt deriving (Show) newtype FMT = FMT (MonoType FMT) class Types a where freeVars :: a - [Var] instance Types FMT where freeVars (FMT (TyVar x)) = [x] freeVars (FMT (TyConst _ xs)) = nub . concatMap freeVars $ xs main = print $ freeVars (FMT (TyConst foo [(FMT (TyVar abc)), (FMT (TyVar 123)), (FMT (TyConst bar [(FMT (TyVar www))]))])) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
Brandon Moore wrote:
I don't quite understand the problem, but maybe an example involving an
explicit recursion operator will help.
-- Maybe he's looking for something like...
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
import List
type Var = String
type Const = String
data MonoType mt = TyVar Var
| TyConst Const [mt] deriving (Eq, Show)
newtype Fix f = In { out :: f (Fix f) }
class Types a where
freeVars :: a - [Var]
instance Types (a (Fix a)) = Types (Fix a) where
freeVars (In x) = freeVars x
instance Types a = Types (MonoType a) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
main = do
print $ freeVars
(TyConst
foo
[(In (TyVar abc)),
(In (TyVar 123)),
(In (TyConst
bar
[(In (TyVar www))]))]))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
Christophe Poucet wrote:
What I would like to do is combine HasVars and Type (mostly because in my
framework the two concepts shouldn't be divided from a design perspective)
into one type class to clean it up a bit. However I fail to see how I would
implement toType and fromType for the given instance. Is this feasible
without resorting to ugly hacks?
{-# OPTIONS -fglasgow-exts #-}
-- Multiparameter type classes?
import List
type Var = String
type Const = String
data MonoType mt = TyVar Var
| TyConst Const [mt] deriving (Eq, Show)
data PolyType mt = TyPoly [Var] mt deriving (Show)
class Type a b where
toType :: b - a b
fromType :: a b - b
freeVars :: a b - [Var]
occurs :: Var - a b - Bool
instance Type MonoType Int
-- yada, yada, yada...
instance Type MonoType (MonoType Int) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) $ xs
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] A road for Haskell into the kernel of a full-fledged OS
Joel Reymont wrote: I think this is an awesome idea. I believe the folks at Galois have customized the Haskell runtime for embedded devices but... I wonder if us mere mortals will spend more time fighting laziness (and thus high memory usage) than focusing on driver functionality. In a similar vein, the Coyotos Project ( http://coyotos.org/ ) is writing their own language, BitC, to support their microkernel... http://www.coyotos.org/docs/bitc/spec.html BitC is conceptually derived in various measure from Standard ML, Scheme, and C. Like Standard ML [10], BitC has a formal semantics, static typing, a type inference mechanism, and type variables. Like Scheme [8], BitC uses a surface syntax that is readily represented as BitC data. Like C [1], BitC provides full control over data structure representation, which is necessary for high-performance systems programming. The BitC language is a direct expression of the typed lambda calculus with side effects, extended to be able to reflect the semantics of explicit representation. Greg Buchholz ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Tips for converting Prolog to typeclasses?
Robert Dockins wrote: To make this work, you're going to have to convince the compiler to accept overlapping instances and then make sure they don't overlap :) In the second instance, what you really want to say is instance c [a] c, only where c is not an application of (-). As I recall, there is a way to express such type equality/unequality using typeclasses, but I don't remember how to do it offhand. Now that I think about it more, I see what you are saying. And I think we can be a little more general than c is not an application of (-). A better statement might be c is not a function application which takes an 'a' as the first argument. That should allow us to have a function of type Int-Int-Double-String return a function Double-String when applied to a list of Int's. So in Prolog... :- op(1000,xfy,=). app(A=B,[A],C) :- app(B,[A],C). app(C,[A],C) :- not(isfuncwithhead(C,A)). isfuncwithhead(A=B,A). ...Now I just need to figure out how to represent not without cut. I'll take a look at what Oleg has done. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tips for converting Prolog to typeclasses?
Robert Dockins wrote:
] In the second instance, what you really want to say is instance c [a]
] c, only where c is not an application of (-). As I recall, there is
] a way to express such type equality/unequality using typeclasses, but
] I don't remember how to do it offhand.
For those playing along at home, here's the less general version
which uses Oleg Kiselyov's IsFunction relation and associated TypeCast
machinery from the HList paper...
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
data HTrue
data HFalse
class IsFunction a b | a - b
instance TypeCast f HTrue = IsFunction (x-y) f
instance TypeCast f HFalse = IsFunction a f
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 Apply a b c where -- | a b - c where
apply :: a - b - c
instance Apply b [a] c = Apply (a-b) [a] c where
apply f [] = error Not enough arguments
apply f (x:xs) = apply (f x) xs
instance IsFunction c HFalse = Apply c [a] c where
apply f _ = f
main = do print (apply g [(1::Int)..] ::String)
g :: Int - Int - Int - Int - String
g w x y z = show $ w*x + y*z
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Tips for converting Prolog to typeclasses?
Lately, in my quest to get a better understanding of the typeclass system, I've been writing my typeclass instance declarations in Prolog first, then when I've debugged them, I port them over back over to Haskell. The porting process involves a lot trial and error on my part trying to decide when to use functional dependencies and which compiler extension to enable ( -fallow-undecidable-instances, -fallow-overlapping-instances, etc.). Which might be okay, but I still can produce things that won't compile, and I don't necessarily know if I'm making a fundamental mistake in a program, or if there's something trivial that I'm not doing quite right. For example, there was a question on haskell-cafe last week about creating an apply function. My first solution ( http://www.haskell.org//pipermail/haskell-cafe/2006-May/015905.html ) was to use type classes and nested tuples for the collection of arguments. This works fine. But then I wanted to try to get closer to what the original poster wanted, namely to use regular homogenous lists to store the arguments. So I thought I could reuse the class definition and just provide new instances for a list type, instead of the nested tuple type. Here's the class definition... class Apply a b c | a b - c where apply :: a - b - c ...So I wrote the following Prolog snippets which seemed like they might properly describe the situation I was looking for... :- op(1000,xfy,=). % use = instead of - for arrow type app(A=B,[A],C) :- app(B,[A],C). app(C,[A],C). ...which I translated into the following Haskell instances... instance Apply b [a] c = Apply (a-b) [a] c where apply f [] = error Not enough arguments apply f (x:xs) = apply (f x) xs instance Apply c [a] c where apply f _ = f ...and here's a test program... g :: Int - Int - Int - Int - Int g w x y z = w*x + y*z main = do print $ apply g [1..] ...but I haven't been able to get GHC to accept this yet. So I'm wondering if there's an easy route to learning this stuff. Some sort of comprehensive tutorial out there which I should be reading that describes what should be possible with Haskell's typeclasses plus GHC extenstions, and when and where to enable these extentions. (Bonus points awarded if it explains things in terms of Prolog). Or is this just one of those things that requires reading lots of papers on each extentsion and possibly the source code of the implementation? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Applying Unknown Number Arguments to A Partial Function
Aditya Siram wrote:
] I am trying to write a function 'applyArguments' which takes a
] function and a list and recursively uses element each in the list as
] an argument to the function. I want to do this for any function taking
] any number of arguments.
]
] applyArgument f (arg) = f arg
] applyArgument f (arg:args) = applyArgument (f arg) args
]
] This has failed in Hugs, so my question is: Can I conceptually do
] this? If so, what is the type signature of this function?
OK, here's a program that is similar to your applyArgument. Instead
of the arguments in a list, it stores them in a nested tuple, so that we
can have different types of arguments. You'll have to use the -98
option when using Hugs. Also, it doesn't seem to interact well with
type inference, so I had to provide type signatures for the function f
and some of the parts of args. Anyone know of a better way to define
Apply so we could eliminate these type signatures?
{-# OPTIONS -fglasgow-exts #-}
class Apply x y z | x y - z where
apply :: x - y - z
instance Apply (a-b) a b where
apply f x = f x
instance Apply b as c = Apply (a-b) (a,as) c where
apply f (x,xs) = apply (f x) xs
f :: Int - Double - String - Bool - Int
f x y z True = x + floor y * length z
f x y z False= x * floor y + length z
args = (1::Int,(3.1415::Double,(flub,True)))
main = print $ apply f args
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Applying Unknown Number Arguments to A Partial Function
Aditya Siram wrote:
] I am trying to write a function 'applyArguments' which takes a function and
] a list and recursively uses element each in the list as an argument to the
] function. I want to do this for any function taking any number of arguments.
]
] applyArgument f (arg) = f arg
] applyArgument f (arg:args) = applyArgument (f arg) args
]
] This has failed in Hugs, so my question is: Can I conceptually do this? If
] so, what is the type signature of this function?
It seems like it should be doable, but I'm not enough of a Haskell
wizard to figure it out. But here is my thought process, FWIW. First
off, since you want it to work for *any* function, we know that it can't
use lists, since in Haskell all list elements have to have the same
type. Nested tuples, like (1,(foo,(3.14,Nil))) can have elements of
arbitrary types, so that's a possibility for the container storing the
function's arguments. Next we'll note that the return type of
applyArgument can be different depending on the input argument types.
For example, lets invent a function and some possible argument
lists...
foo x y z = x + y + z
one = (1,Nil)
two = (1,(2,Nil))
three = (1,(2,(3,Nil)))
...so the type of applyArgument foo three would be Integer, while the
type of applyArgument foo two would be Integer-Integer, and the type
of applyArgument foo one would be Integer-Integer-Integer. But
Haskell doesn't allow a single function to different types. What we can
do though, is define an infinite family of functions which have
different types, but share the same name. That is the purpose of type
classes. Here's a fun example that I like...
instance Num a = Num [a] where
(+) = zipWith (+)
...that little snippet says that whenever we have a list of type a
(the [a]), where a is also in the class Num, then we can add two of
those lists together. So now something like [1,2,3]+[4,5,6] is legal.
But that also happens to be a recursive definition since a list like
[1,2,3] is now also in class Num. So things like...
[[1,2,3],[4,5,6]] + [[7,8,9],[0,1,2]]
[[1,2,3]] + [[4,5,6]]
...will also work. Now here is where I run into trouble. The code
below is what I think you should be able to do to define applyArgument
(shortened to app), but it doesn't quite work, failing with a type
error...
Illegal instance declaration for `Apply (a - b) b (a, c)'
(the instance types do not agree with the functional dependencies of the
class)
In the instance declaration for `Apply (a - b) b (a, c)'
...Maybe someone can chime in to correct me, or point out the flaw in my
thinking.
{-# OPTIONS -fglasgow-exts #-}
data Nil = Nil -- A type to terminate our nested tuples
class Apply a b c | b-c where
app :: (a-b) - (a,c) - b
-- base case: ran out of arguments, so stop recursion
instance Apply a b Nil where
app f (x,Nil) = f x
-- recursive case: If types a, b, and c are member of the
-- class Apply, then the types (a-b), b, and (a,c) are
-- also a member, so keep going...
instance Apply a b c = Apply (a-b) b (a,c) where
app f (x,rest) = app (f x) rest
g w x y z = w*x + y*z
args = (1,(2,(3,(4,Nil
main = print $ app g args
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Applying Unknown Number Arguments to A Partial Function
Greg Buchholz wrote: instance Apply a b c = Apply (a-b) b (a,c) where Whoops, instead of that, I think I meant... instance Apply (b-c) c d = Apply (a-b-c) (b-c) (a,d) where ...where we strip off one layer of types, because of the recursion. Of course, that still doesn't work though. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial Derivatives
Gerhard Navratil wrote: I need a library that provides partial derivatives for functions. The solution I came up with is based on a datatype using reversed polish notation to store the function: I like Oleg Kiselyov's Typeful symbolic differentiation of compiled functions... http://www.haskell.org/pipermail/haskell/2004-November/014939.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
Neil Mitchell wrote: Now lets define super show which takes a function, and prints its code behind it, so: superShow f = not superShow g = \x - case ... now superShow f /= superShow g, so they are no longer referentially transparent. OK. I'm probably being really dense today, but where did g come from? Is this is the internal definition of not? And does this loss of referential transparency contaminate the rest of the language, or is this superShow just an anomaly? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
Brian Hulley wrote: ] Here is another example. Consider two functions f and g which, given the ] same inputs, always return the same outputs as each other such as: ] ] f x = x + 2 ] g x = x + 1 + 1 ] ] Now since f and g compute the same results for the same inputs, anywhere in ] a program that you can use f you could just replace f by g and the ] observable behaviour of the program would be completely unaffected. This is ] what referential transparency means. ] ] However, if you allowed a function such as superShow, superShow f == x + ] 2 and superShow g == x + 1 + 1 so superShow f /= superShow g thus you ] could no longer just use f and g interchangeably, since these expressions ] have different results. Hmm. It must be a little more complicated than that, right? Since after all you can print out *some* functions. That's what section 5 of _Fun with Phantom Types_ is about. Here's a slightly different example, using the AbsNum module from... http://www.haskell.org/hawiki/ShortExamples_2fSymbolDifferentiation import AbsNum f x = x + 2 g x = x + 1 + 1 y :: T Double y = Var y main = do print (f y) print (g y) ...which results in... *Main main (Var y)+(Const (2.0)) (Var y)+(Const (1.0))+(Const (1.0)) ...is this competely unrelated? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multiple computations, same input
Neil Mitchell wrote: I suspected that you actually wanted to do something cleverer with the list, for the sake of argument, I'm going to change 1 to p1 and 2 to p2 - to show how this can be done in the general case. With the specific information you know about 1 vs 2 you can do better, but this gets across the general point: f lst = show (sumPairs (1) (2) lst) sumPairs :: (Int - Bool) - (Int - Bool) - [Int] - (Int, Int) sumPairs p1 p2 [] = (0, 0) sumPairs p1 p2 (x:xs) = (add p1 a, add p2 b) where (a,b) = sumPairs xs add pred value = if pred x then x+value else value [Untested, something like this should work] Nope. That won't work because you end up creating huge add thunks which cause end up causing a stack overflow (tested with GHC -O2). I think you are probably going to need strictness in order to skin this cat in Haskell. Here's an example that does work... import Data.List main = print $ para_filter_sum ( 1) ( 2) lst twos = 2: twos lst = take 1000 $ [1,2,3,4,5] ++ twos -- f lst = show (filter ( 1) lst, filter ( 2) lst) para_filter_sum f g xs = foldl' (\(n,m) elem - seq n $ seq m $ (n+if f elem then elem else 0, m+if g elem then elem else 0 ) ) (0,0) xs Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multiple computations, same input
Tomasz Zielonka wrote: I wonder if it would be possible to remove the space-leak by running both branches concurrently, and scheduling threads in a way that would minimise the space-leak. I proposed this before http://www.haskell.org/pipermail/haskell-cafe/2005-December/013428.html FWIW, (not much), I asked a similar questions over on the Lambda-the-Ultimate blog a while back... http://lambda-the-ultimate.org/node/923 http://lambda-the-ultimate.org/node/485 ...Anyway, I can't help but think that there might be a happy medium between eager and lazy evaluation. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Eval of a syntax tree for reduction
Steve Downey wrote:
] 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
] }
]
] I'm looking for some suggestions on the direction to proceed.
If you are looking to get rid of the noise caused by Maybe, you
could package up all of the case and Just stuff into a few reusable
functions. In fact, its already been done for you, since Maybe is a
monad...
http://www.nomaware.com/monads/html/maybemonad.html
...You could try something like...
import Control.Monad -- for liftM3, etc.
eval1_ :: ArithExpr - Maybe ArithExpr
eval1_ (TmIfExpr TmTrue t _) = return t
eval1_ (TmIfExpr TmFalse _ t) = return t
eval1_ (TmIfExpr t1 t2 t3) = liftM3 TmIfExpr (eval1_ t1) (return t2) (return
t3)
...and if it turns out you don't like the resulting Maybeified
program, you can get the original functionality back by changing the
type signature to use the Identity monad instead of Maybe.
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Deepest functor [was: fmap for lists of lists of lists of ...]
[EMAIL PROTECTED] wrote: 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. Excellent. I guess I'll be brushing up on my typeclass-fu in order to figure out how all this works. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Deepest functor [was: fmap for lists of lists of lists of ...]
[EMAIL PROTECTED] wrote: 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. Excellent. I guess I'll be brushing up on my typeclass-fu in order to figure out how all this works. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] fmap for lists of lists of lists of ...
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: ([],[[]],[[[]]],...)? Does that make sense? This doesn't work... class Funct f where f_map :: (a - b) - f a - f b instance Funct [] where f_map = map instance Funct a = Funct [a] where f_map f = map (f_map f) main = print $ fmap (+1) [[[1,2,3]]] ...but maybe it gets the idea across? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Trying to get a Composite design pattern to work
Asfand Yar Qazi wrote:
I'm trying to implement hierarchical states in Haskell, following on from my
work at doing them in C++.
Here's what I've got so far:
data StateNode a= CompositeState [ StateNode a ] | State a
stateslist :: StateNode a - [a]
stateslist(State x) = [x]
stateslist(CompositeState xs) = {- return list of objects of type a -}
The following give errors (as they should)
-- stateslist(CompositeState xs) = [ stateslist(x) | x - xs ]
-- stateslist(CompositeState xs) = map stateslist xs
You see what I'm trying to do? This is how I want it to behave:
sm1 = CompositeState [ State 1, State 2, State 3 ]
stateslist(sm1)
= [1, 2, 3]
Maybe...
stateslist :: StateNode a - [a]
stateslist (State x) = [x]
stateslist (CompositeState xs) = concatMap stateslist xs
Greg Buchholz
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Looking for a random-access sequence data structure
Duncan Coutts wrote: I've been looking around (unsuccessfully) for an efficient data structure to implement a sequence data type with indexed insert/delete/lookup. See also, Robert Will's Democratic Sequences which strive for O(log n) complexity for all major operations... Democratic Sequences: an Abstract Sequence Data Type which is not optimised for some algorithms (as Deques and many other implementations are), but which aims to provide a very simple and consistent interface for day-to-day programming and prototyping, where any sensible operation runs with acceptable performance, although possible none is optimal. ...unfortunately the write-up and code seems to have lost its home, so you'll have to get it from the Google cache ( http://xrl.us/jjs9 ). Greg Buchholz ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Statements spanning multiple lines?
Daniel Carrera wrote: Hi all, How do I write a statement that spans multiple lines? I have this function: pythagoras n = [(a,b,c) | a -[1..n], b -[1..n], c -[1..n], a = b, b c, a*a + b*b == c*c] This should all be in one line. I know some ways to make the line shorter, like defining local functions and using 'filter'. But the code would be clearer if I could just make this one statement span several lines. Haskell's layout rules mean that you have to keep intenting at the beginning of a line to continue a definition. Try something like... pythagoras n = [(a,b,c) | a - [1..n], b - [1..n], c - [1..n], a = b, b c, a*a + b*b == c*c ] ...or... pythagoras n = [(a,b,c) | a - [1..n], b - [1..n], c - [1..n], a = b, b c, a*a + b*b == c*c ] ...See also... http://www.haskell.org/onlinereport/lexemes.html#lexemes-layout Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Statements spanning multiple lines?
You might also like to try the slightly more efficient... pyth n = [(a,b,c) | a - [1..n], b - [a..n], c - [a+1..n], a*a + b*b == c*c ] Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can't Haskell catch up with Clean's uniqueness typing?
[EMAIL PROTECTED] wrote: It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside). snip programs generated by ghc generally need multiples of time and space of the Clean version, even though the latter is, in many cases, a nearly literal translation from Haskell. Maybe you'd be interested in Hacle? http://www-users.cs.york.ac.uk/~mfn/hacle/ The aim was to develop a translator which is capable of reading in any given Haskell'98 program and writing out a semantically equivalent Clean one. Why? To investigate the suitability of the Clean compiler for compiling Haskell programs, i.e. Can the Clean compiler, in combination with this tool, produce faster executables than existing Haskell compilers? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Existentially-quantified constructors, Eq and Show
Joel Reymont wrote: Folks, Is there a less verbose way of doing this: data State a = Start | Stop | (Show a, Eq a) = State a I'm curious, what is the difference between the above and... data State a = Start | Stop | State a deriving (Show, Eq) ...Does it give better error messages at compile time or something? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type classes and hFoldr from HList
Ralf Lammel wrote: What you can do is define a dedicated *type code* for composition. comp = hFoldr (undefined::Comp) (id::Int - Int) test data Comp instance Apply Comp (x - y,y - z) (x - z) where apply _ (f,g) = g . f That does it! Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type classes and hFoldr from HList
I was playing around with the HList library from the paper...
Strongly typed heterogeneous collections
http://homepages.cwi.nl/~ralf/HList/
...and I thought I'd try to fold the composition function (.) through a
heterogeneous list of functions, using hFoldr...
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
import CommonMain
main = print $ comp abc
test = HCons ((+1)::(Int-Int)) (HCons ((*2)::(Int-Int)) (HCons length HNil))
comp = hFoldr (.) id test
instance Apply (a - b - c - d) (a, b) (c - d)
where
apply f (a,b) = f a b
...but it fails with the following type error...
]Compiling Main ( compose.hs, interpreted )
]
]compose.hs:10:7:
]No instances for (Apply ((b - c) - (a - b) - a - c)
](Int - Int, r)
]([Char] - a3),
] Apply ((b - c) - (a - b) - a - c) (Int - Int, r1)
r,
] Apply ((b - c) - (a - b) - a - c) ([a2] - Int, a1
-a1) r1)
] arising from use of `hFoldr' at compose.hs:10:7-12
]Probable fix:
] add an instance declaration for (Apply ((b - c) - (a - b) - a - c)
] (Int - Int, r)
] ([Char] - a3),
] Apply ((b - c) - (a - b) - a - c)
](Int - Int, r1) r,
] Apply ((b - c) - (a - b) - a - c)
]([a2] - Int, a1 - a1) r1)
]In the definition of `comp': comp = hFoldr (.) id test
...Anyway, I couldn't quite tell whether I was using hFoldr incorrectly,
or if I needed to have more constraints placed on the construction of
test, or if needed some sort of type-level function that resolves...
Apply ((b - c) - (a - b) - a - c)
...into (a - c), or something else altogether. I figured someone might
be able to help point me in the right direction.
Thanks,
Greg Buchholz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Working inside the fold
Recently I've been browsing some of Oleg Kiselyov's articles entitled Towards the best collection traversal interface... http://okmij.org/ftp/Computation/Continuations.html#enumerator-stream A programming language system gives us typically one of the two interfaces to systematically access elements of a collection. One traversal API is based on enumerators -- e.g., for-each, map, filter higher-order procedures -- of which the most general is fold. The second approach relies on streams, a.k.a. cursors, lazy lists. ...where he argues that (since they're both intraconvertible) a default enumerator/fold choice is better than the lazy-list approach. I was sufficiently intrigued I thought I'd take up the challenge and see what could be done working inside the fold. This message is literate Haskell source, for those of you playing at home. The first thing to do is define a few folds which will take the place of lists. I'll start out with a finite and infinite one... numsTo10 f unit = foldr f unit [1..10] nats f unit = foldr f unit [1..] If you want the sum of the first ten naturals you'd invoke it as... *Main numsTo10 (+) 0 55 ...and to see that you can convert back to a list... *Main numsTo10 (:) [] [1,2,3,4,5,6,7,8,9,10] That's nice, but the first thing you'll notice is that while there are numerous list processing functions in the prelude, there are none for specifically working inside a fold. Let's try and define a few... map_ :: (a - b) - (b - c - d) - a - c - d map_ f g a b = g (f a) b ...so if we want the sum of the first ten squares... *Main numsTo10 (map_ (^2) (+)) 0 385 ...or the actual list... *Main numsTo10 (map_ (^2) (:)) [] [1,4,9,16,25,36,49,64,81,100] ...Filter is also a nice function... filter_ p f a b = if p a then f a b else b *Main numsTo10 (filter_ odd (:)) [] [1,3,5,7,9] ...and we can also play nice with infinity... takeWhile_ unit p f a b = if p a then f a b else unit *Main nats (takeWhile_ [] (15) (:)) [] [1,2,3,4,5,6,7,8,9,10,11,12,13,14] ...That's a little bit ugly because you have to supply the unit value (in this case []) for the fold to takeWhile_. The dropWhile_ function is also a little quirky, since it uses the tupling trick from... A Tutorial on the Universality and Expressiveness of Fold http://citeseer.ist.psu.edu/hutton93tutorial.html dropWhile_ p f a (ys, xs) =((if p a then ys else f a xs), f a xs) *Main numsTo10 (dropWhile_ (5) (:)) ([],[]) ([5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10]) *Main numsTo10 (dropWhile_ (5) (+)) (0,0) (45,55) ...where the first member of the pair is the desired answer. If you want to do more than one thing inside the fold, fork might be the solution (is there a better name?) fork f g z (x,y) = (f z x, g z y) *Main numsTo10 (fork (:) (+)) ([],0) ([1,2,3,4,5,6,7,8,9,10],55) *Main numsTo10 (fork (filter_ odd (:)) (fork (+) (*))) ([],(0,1)) ([1,3,5,7,9],(55,3628800)) ...And you can mostly compose these operations, although for infinite lists you'll hit bottom if anything other than takeWhile_ is the first function... c = nats (takeWhile_ ([],(0,1)) (20) (filter_ even (map_ (^2) (fork (:) (fork (+) (*)) ([],(0,1)) *Main c ([4,16,36,64,100,144,196,256,324],(1140,34519618525593600)) ...So a few generic munging functions can be defined for inside the fold. I couldn't think of how to define take or drop or figure out what a zipWith would mean. Are there any other interesting functions that could be defined? Is there a better way define these functions? Is there anything other than curiosity which would motivate someone to use these functions? FWIW, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Trapped by the Monads
Mark Carter wrote: What struck me was this bit of code: assemblyLine w = (return w) = makeChopsticks = polishChopsticks = wrapChopsticks Interestingly, this looks like Forth (!), where you put a value on the stack, and successive operations fiddle with the stack as a series of transformations. Not that I know Forth, you understand. Hmm, so Haskell can be a concatenative language if you want it to be. You might also like take a look the Joy language... http://www.latrobe.edu.au/philosophy/phimvt/joy.html ...sort of a functional, higher level cousin of Forth. In Joy, you create programs by composing functions with other functions. This is in contrast to other languages where functions are mainly applied to other functions (and data). The composition operator Joy is denoted by white space. This is similar to the way juxtaposition is used to denote function application in more conventional languages. (i.e., in Joy f g means g composed with f, while in other languages f(g) means apply function f to argument g). Now, what if we had a name for this implicit composition operation? We could then modify it to do a whole host of other things with the functions f and g besides just the boring old composition (like maybe skipping the execution of g if f fails, or allowing backtracking, or something more bizarre and clever). And what should we name this new super composition operator? = maybe? Ah... Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] Haskell versus Lisp
Bill Wood wrote: As to utility, quite the contrary, I think. Offhand I can think of the screamer package for Common Lisp, which provides non-deterministic mechanisms for use in backtracking applications. For a while in the 80's there was practically a cottage industry implementing various flavors of Prolog and other Logic Programming languages in Lisp; one notable example was LogLisp. I think the goal was to present an application where Lisp macros made for a more succinct program than the equivalent Haskell version. http://www.google.com/search?q=backtracking+monad Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Practical introduction to monads
Paul Moore wrote: One thing I haven't found a really good discussion of, is practical examples of building monads. There's plenty of discussion of the IO monad, and the state monad, and a lot of good theory on monads, but although I've seen tantalising statements about how powerful the ability to define your own monads can be, but no really concrete examples - something along the lines of - here is problem X - this might be our first cut at coding it - we can abstract out this stuff, as a monad - see how the code looks now, how much cleaner it is Maybe you could try going in the opposite direction, and convert something like monadic parser combinators... http://www.cs.nott.ac.uk/~gmh/bib.html#pearl ...it into their non-monadic form (explictly passing the parsed string around). I've only skimmed - so pointers to areas in these documents I might have missed would be appreciated. On the other hand, pointers to papers I've missed altogether would also be gratefully received. I found the papers by Philip Wadler to be the most helpful... http://homepages.inf.ed.ac.uk/wadler/topics/monads.html ...especially _Monads for functional programming_ and _Imperative functional programming_. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Lists vs. Monads
Here's a question for the Haskell community that I've been wrestling with lately. When we say lists are monads what does that mean? I can see one of two things. First the slightly superficial... A.) Lists can be made members of the Monads class, and you can define a couple of functions, bind and return that obey the Three Laws. ...or the more fundamental... B.) Monads somehow define lists. If you had a version of Haskell without recursive data types you wouldn't be at a loss, because you could always use monads to recreate lists. Maybe bind would replace the job of cons and return would replace head or somesuch. I'm of the mind that A.) is the right interpretation, but I've seen the lists are monads meme mentioned enough that I sometimes question it. In fact, I had a hard time articulating B.) because I don't know what the other possibilies are. In case it isn't clear enough, here's another analogy... A.) Insects are cold blooded animals. ...while that is 100% true, many other animals are cold blooded. It doesn't get at the essence of what it means to be an insect. Compare with a statment like... B.) Insects are six-legged animals with an exoskeleton. ...which tells us a lot more about the fundamental nature of insects. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Template Haskell Question: Spliced expr. of type TypeQ
Eike M. [EMAIL PROTECTED] wrote: I was wandering if I could do something similar to Depended Types using Template-Haskell. The documentation of GHC (6.2.2 and 6.4) says that a splice may occur in place of a type, but I get a parse error when I try that. From the TH homepage (http://www.haskell.org/th/)... Not all of even the original design has been implemented yet. The known issues are: * You can only splice in lists of declarations and expressions, not * types, patterns etc ..and it gives a link... http://haskell.org/pipermail/template-haskell/2003-February/21.html Maybe that's the key? Greg Buchholz ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] resolving missing class instances @ compile time
Bernard Pope wrote: Perhaps this section of the report might help: From Section 4.3.2 Instance Declarations in the Haskell Report: http://www.haskell.org/onlinereport/decls.html#instance-decls If no binding is given for some class method then the corresponding default class method in the class declaration is used (if present); if such a default does not exist then the class method of this instance is bound to undefined and no compile-time error results. I may be missing the big picture, but why is this behavior more desirable than failing with an error at compile time? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] resolving missing class instances @ compile time
Samuel Bronson wrote: Aren't the warnings just about as usefull as failures? Anyway, you could always use the -Werrror flag for ghc... In any case, I would not like to have to implement an entire typeclass at once... it would interfere with incremental development. Hmm. I guess I'm doing a terrible job of asking my question. I don't want to implement the entire typeclass either. Just the part that my program actually uses. Why can't the fact that my program uses an unimplemented instance of a class be statically determined? Is there a theoretical reason it can't be done? Is it more convienient for compiler/specification writers this way? Is it just because that's the way its always been done? Curious, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] resolving missing class instances @ compile time
Samuel Bronson wrote: After thinking about it for a while, I'm positive it would be a LOT of work to get that to work in general, if it is even possible. Even getting it to work in only specific, limited cases (such as within a module) would probably not be easy, since it is such an indirect kind of thing. It probably wouldn't be all that usefull anyway, either. (This is my last time, I promise). Why? Here's my thought process. Let's say I a have a program like... main = print $ (foo 42) ...(that's the whole thing). The compiler parses it, determines that foo is a function being applied to 42 and tries to look up foo in the symbol table. That fails because there is no function foo. Why is it any different if foo is part of some type class? We must know where to look for foo since we know the type of foo from its arguments and return value (it passed the type checker after all). Confused, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] resolving missing class instances @ compile time
Samuel Bronson wrote: The former may not be hard, but the latter would require functions with typeclass constraints on their types to be annotated in the interface file with what typeclass methods they called. Does that sound hard yet? Compared to writing the rest of the compiler? No. I've never written a Haskell compiler, but I'd say it sounds like it might be a tedious book-keeping problem though. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Squashing space leaks
Josef Svenningsson wrote: I think the thing that really kills you is the way you shuffle around the list in the advance function. Your commented out rotations function has the same problem. Here is my attempt to solve the problem a little more efficiently: We're heading in the right direction anyway. I can now compute 1 million iteration in about 2 minutes (with +RTS -H750M -K100M). Well almost, since it now doesn't compute the right answer, so something must be amiss in the shuffling section. Now if we can get it to us a little less than 1G of memory, we'll be in good shape. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Speed comparison?
Aaron Denney wrote: On 2005-05-03, David Roundy [EMAIL PROTECTED] wrote: An interesting challenge would be to rewrite fftw in haskell, and see how close one could come to the performance of the original... :) What precisely do you mean by that? FFTW is C code generated by OCaml? Do you want to retarget ti so that Haskell is generated, or rewrite the generator in Haskell? (Or both?) Maybe not completely related, but you might find this paper interesting... http://lambda-the-ultimate.org/node/view/652 Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to speed things up
Dmitry Vyal wrote: Hello everybody. I have a long list consisted of a small number (about a dozen) of elements repeating in random pattern. I know all the possible elements. I need to count number of occurences of each particular element and to do i quickly. For example quick_func Eq a = [a] - [(a,Int)] quick_func [1,2,3,1,2,9,1,9] == [(1,3),(2,2),(3,1),(9,2)] According to profiler this function is the bottle-neck in my sluggish program so I really need to speed it up. What's been tried so far? Below is a snippet using arrays. You'd probably get a faster program with Unboxed arrays and unsafeAccumArray. import Data.Array main = print $ quick_func [1,2,3,1,2,9,1,9] quick_func is = assocs $ accumArray (+) 0 (1,12) [(i, 1) | i-is] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to speed things up
Dmitry Vyal wrote: By the way, how to use Unboxed arrays and unsafeAccumArray Greg Buchholz mentioned? I can't find them in GHC 6.2 documentation. http://www.haskell.org/~simonmar/haddock-example/Data.Array.Base.html Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linux device drivers
Mark Carroll wrote: I was wondering about the possibility of using Haskell for developing device drivers that would be kernel modules for Linux. If nothing else, it would be quite an educational experience for me, as I've not yet experimented with either the Linux kernel or Haskell FFI, nor have I had to learn how to squeeze much performance out of my Haskell code. Clearly, this application demands special things from the compiler and the runtime. But, I'm not exactly sure what, nor how to achieve such given current compilers. Does anyone have any thoughts? You might be interested in hOp: hOp is a micro-kernel based on the RTS of GHC. It is meant to enable people to experiment with writing device drivers in Haskell. http://www.macs.hw.ac.uk/~sebc/hOp/ or maybe House... http://www.cse.ogi.edu/~hallgren/House/ Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: The things to notice are using types as instance labels, that constraints form horn clause compile time meta-programs (in a non-backtracking prolog style) and that multi-parameter classes with functional depandencies simulate some dependant types. I think I understood everything in that sentance up to the word as ;-) Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: Haskell is not dependantly typed, so cannot deal with types that depend on values. Can anyone recommend a nice dependently typed language to play with? Cayenne, Epigram, other? Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote: I have refactored your code into a type level Haskell program. This has the nice advantage that it is extensible. Wow. Color me impressed. A little under a week ago, I stumbled onto Joy, and thought to myself that it could be translated almost directly into Haskell (which would imply it was possible to statically type). Well, it wasn't quite as direct as I had initially thought, but it looks like you've done it. Are there any papers/books out there which I could study to learn more about these (and other) tricks of the type system wizards? Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Keean Schupke wrote:
I dont see why this is illegal... what do we want? take the top two
items from the stack?
With the code below (direct translation from tuples to HLists) I
still get an occurs check error when trying to define fact5...
Compiling Main ( joy3.hs, interpreted )
joy3.hs:23:
Occurs check: cannot construct the infinite type: l = HCons e l
Expected type: HCons
(HCons e (HCons e l) - HCons e l)
(HCons
(HCons e3 l3 - HCons e3 (HCons e3 l3))
(HCons
(HCons e1 l2 - HCons e1 l2)
(HCons (HCons e2 l1 - HCons Bool l1) a)))
- c
Inferred type: HCons
(HCons e (HCons e l) - HCons e (HCons e l))
(HCons
(l4 - l4)
(HCons (l4 - HCons e (HCons e l))
(HCons (l4 - l5) l4)))
- HCons e (HCons e l)
In the second argument of `(!)', namely `linrec'
In the definition of `fact5':
fact5 = quote (nul)) ! (quote (suc))) ! (quote (dup ! pre)))
! (quote (mult)))
! linrec
Failed, modules loaded: MainGhcGeneric1, TypeCastGeneric1, Label3,
TypeEqGeneric1, TypeEqBoolGeneric, GhcExperiments, GhcSyntax,
CommonMain, Datatypes2, Variant, TIC, TIP, HTypeIndexed, GhcRecord,
Record, HZip, HOccurs, HArray, HListPrelude, FakePrelude.
Looks to me like a very similar error to the tuple case.
Greg Buchholz
--Joy combinators in Haskell
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}
import MainGhcGeneric1
import Data.Typeable
main = do print $ ((lit 10)!(lit 4)!mult) bot -- 4*10
print $ ((lit 3) ! cube ) bot-- 3^3
print $ ((lit 4) ! fact5) bot-- 4!
bot = HNil
square = dup ! mult
cube = dup ! dup ! mult ! mult
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub
--In Joy: [null] [succ] [dup pred] [*] linrec
fact5 :: HCons Integer a - HCons Integer a
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec
--}
--primitive combinators
(!) f g = g.f
i(a, b) = (a b)
add (HCons a (HCons b c)) = (HCons (b+a) c)
sub (HCons a (HCons b c)) = (HCons (b-a) c)
mult (HCons a (HCons b c)) = (HCons (b*a) c)
swap (HCons a (HCons b c)) = (HCons b (HCons a c))
pop (HCons a b) = b
dup (HCons a b) = (HCons a (HCons a b))
dip (HCons a (HCons b c)) = (HCons b, (a c))
eq (HCons a (HCons b c)) | a == b= (HCons True c)
| otherwise = (HCons False c)
ifte (HCons f (HCons t (HCons b stack)))
| hHead(b stack) = (t stack)
| otherwise = (f stack)
linrec (HCons rec2 (HCons rec1 (HCons t (HCons p stack
| hHead (p stack) = (t stack)
| otherwise = rec2 (linrec (HCons rec2
(HCons rec1
(HCons t
(HCons p (rec1 stack))
lit val stack = (HCons val stack)
quote = lit
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: Am Freitag, 4. M?rz 2005 19:35 schrieb Greg Buchholz: So, can anyone direct me towards more information on exactly what an Occurs check is, or does anyone see an easy fix to my problems? If I remember correctly, an occurs check is checking whether a type variable (call it 't') occurs as an argument to a tuple constructor or function arrow in a type expression to be substituted for t, as above or in t = t - t1. Such occurences would lead to an infinite type, hence are forbidden. Interesting, I'll have to think it over. (Of course being a relative newcomer to Haskell, I have to do a lot of thinking when it comes to most things.) BTW, can anyone recommend a good introductory resource for learning about type theory? I once flipped through Pierce's Types_and_Programming_Languages, but at first glance, it seemed to be a little advanced for my understanding (the foreign-looking equations per word ratio seemed a little too high). I have a fix for the factorial and similar recursive functions, though it's not really easy (and needs extensions): don't define the recursion combinators via Stack, do it like this: linrec2 :: forall a. (forall b. (a,(a,b)) - (a,b)) - (forall b. (a,b) - (a,(a,b))) - (forall b. (a,b) - (a,b)) - (forall b. (a,b) - (Bool,b)) - (forall b. (a,b) - (a,b)) linrec2 rec2 rec1 t p stack | fst $ p stack = t stack | otherwise = rec2 $ linrec2 rec2 rec1 t p (rec1 stack) Nice. Definitely something for me to study. Of course, IFAICT, the main motivation for Joy is to try and define everything in terms of function composition instead of function application. I don't know Joy, but probably there the stack is (roughly) a heterogenous list, which is hard to model in Haskell, Yeah, I don't know Joy either, other than reading a few documents, but I do think its stack is really heterogenous list. The one reason I was thinking this might be doable in Haskell, is the fact that the few combinators I looked at don't recurse down the whole stack. That, of course, would be a complete nightmare in Haskell. Instead they take a stack, munge a few (finite number of) items at the top, and return another stack. I was hoping that the type variable a in (Integer, a) - (Integer, a) would be amorphous enough to match whatever was left over after grabbing a few items off the top of this stack. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Daniel Fischer wrote: I think, it would be possible to define recursion combinators for specific patterns, like this functions takes 4 elements from the stack, this one 3 and so on, but then you would need combinators for all these patterns, which is rather cumbersome. Hmm. The standard Joy combinators probably can't be typed, so maybe my next step would be to find/create a recursion combinator with a static type. Surely one must exist? If you can have a typed lambda calculus, you must be able to have a typed SK combinator calculus, right? (Now I'm way out of my league.) I'll have to think some more on why you couldn't have a recursion combinator which was more generic than the one that takes 3 items off the stack, or 4 items, rather than n items. Or maybe the whole idea of using a stack is the essential weakness. IMO, it's just not the thing to do things in Haskell exactly like in Joy (or in Java, prolog, or - horribile dictu- in C/C++). Even if it's possible, the spirit of the languages is so different that you should do the same thing in different ways. But of course it's interesting to see whether it can be done. Yeah. I'm only in it for the brain exercise, not to convert the masses over to Joy ;-) ...another stack. I was hoping that the type variable a in (Integer, a) - (Integer, a) would be amorphous enough to match whatever was left over after grabbing a few items off the top of this stack. Well, it's fairly amorphous, but it must be the same type in both type-expressions, and that's why the points-free definition of fact doesn't type-check without the type signature, the 'fact' in the else-branch is used at type (Integer,(Integer,a)) and so on, without the type signature, the type-checker assumes that it must be instantiated at exactly the same type, which it isn't. With the signature, the type-checker knows that 'fact' is polymorphic and that it's perfectly all right to instantiate it at a different type in the recursive call. That pretty much sums up why I thought the whole crazy scheme might work, only in better words. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Joy Combinators (Occurs check: infinite type)
Recently, while investigating the (non-statically typed) stack-based
functional language Joy (http://www.latrobe.edu.au/philosophy/phimvt/joy.html),
I became interested in seeing if I could implement Joy's combinators in
Haskell. I started with a stack based implementation using nested
tuples as the stack. Things worked out well until I got to the
recursion combinators. Even then, things didn't seem that bad, since
Haskell was able to infer types for the the linrec and genrec
combinators. Trouble popped up when I tried to apply the recursion
operators to a function (in this case calculating the humble factorial).
In the code below, fact3,4 5 all fail with an Occurs check that
looks something like the following...
joy3.hs:24:
Occurs check: cannot construct the infinite type: t = (a, t)
Expected type: ((a5 - (a, (a, t)), a5) - (a, t),
((a1, t3) - (a1, (a1, t3)),
((a2, t2) - (a2, t2), ((a3, t1) - (Bool, t1),a4
- c
Inferred type: ((a5 - (a, (a, t)), a5) - (a, (a, t)),
(a5 - a5, (a5 - (a, (a, t)), (a5 - (Bool, b),a5
- (a, (a, t))
...Normally, I would have given up and declared that Joy wasn't an easily
typed language, but I'm motivated to dig further because if you remove
the type signature from fact below, it also fails with an Occurs
check. So, can anyone direct me towards more information on exactly
what an Occurs check is, or does anyone see an easy fix to my
problems?
Thanks,
Greg Buchholz
P.S. The first thing you should note about the code below is the
definition of the reverse composition operator (!), which I used to give
the program a more Joy-like feel. (i.e. (!) f g = g.f)
--Joy combinators in Haskell
main = do print $ ((lit 6) ! fact) bot-- factorial of 6
print $ ((lit 2) ! square ! fact2) bot -- factorial of 4
bot = EOS -- end of stack
square = dup ! mult
cube = dup ! dup ! mult ! mult
--In Joy: factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte
fact :: (Integer, a) - (Integer, a)
fact = (quote ((lit 0) ! eq)) !
(quote (pop ! (lit 1))) !
(quote (dup ! (lit 1) ! sub ! fact ! mult)) !
ifte
--In Joy: [1 1] dip [dup [*] dip succ] times pop
fact2 = (quote ((lit 1) ! (lit 1)))
! dip ! (quote (dup ! (quote mult) ! dip ! suc))
! times ! pop
{- fact3,4 5 don't type check, fails with...
-- Occurs check: cannot construct the infinite type:
--In Joy: [null] [succ] [dup pred] [i *] genrec
fact3 :: (Integer, a) - (Integer, a)
fact3 = (quote nul) ! (quote suc) ! (quote (dup ! pre)) ! (quote (i ! mult))
! genrec
fact4 :: (Integer, a) - (Integer, a)
fact4 = genrec.quote(mult.i).quote(pre.dup).quote(suc).quote(nul)
--In Joy: [null] [succ] [dup pred] [*] linrec
fact5 :: (Integer, a) - (Integer, a)
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec
--}
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub
linrec (rec2, (rec1, (t, (p, stack
| fst (p stack) == True = (t stack)
| otherwise = rec2 (linrec (rec2, (rec1, (t, (p, (rec1 stack))
genrec (rec2, (rec1, (t, (b, stack
| fst (b stack) == True = (t stack)
| otherwise = (rec2.quote(genrec.quote(rec2).quote(rec1).
quote(t).quote(b))) (rec1 stack)
times (p, (n, stack)) | n0 = times (p, (n-1, (p stack)))
| otherwise = stack
(!) f g = g.f
i(a, b) = (a b)
add (a, (b, c)) = (b+a, c)
sub (a, (b, c)) = (b-a, c)
mult (a, (b, c)) = (b*a, c)
swap (a, (b, c)) = (b, (a, c))
pop (a, b) = b
dup (a, b) = (a, (a, b))
dip (a, (b, c)) = (b, (a c))
eq (a, (b, c)) | a == b= (True, c)
| otherwise = (False,c)
ifte (f, (t, (b, stack))) | fst (b stack) == True = (t stack)
| otherwise = (f stack)
lit val stack = (val, stack) -- push literals on the stack
quote = lit
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec and type (IO t) error
This is probably an easy question, but I'm having a problem with parsec in the IO monad. The essential parts of my program looks like this... import Text.ParserCombinators.Parsec main = do input - getContents putStr $ show $ parse_text shape_parse input --(cam, sh) - parse_text shape_parse input --putStr $ (show cam) ++ \n ++ (show sh) putStr \n parse_text p input = case (parse p input) of Left err - error $ Invalid input++(show err) Right x - x shape_parse = do cam - camera_parse shapes - many1 (sphere_parse | plane_parse) return (cam, shapes) -- blah, blah, blah, etc. This works fine in GHC. The types for parse_text and shape_parse are... *Main :t parse_text parse_text :: forall a tok. GenParser tok () a - [tok] - a *Main :t shape_parse shape_parse :: forall st. GenParser Char st (Camera, [Shape]) *Main Now when I change main to... main = do input - getContents --putStr $ show $ parse_text shape_parse input (cam, sh) - parse_text shape_parse input putStr $ (show cam) ++ \n ++ (show sh) putStr \n I get the following message from GHCi... p2.hs:38: Couldn't match `IO t' against `(Camera, [Shape])' Expected type: GenParser Char () (IO t) Inferred type: GenParser Char () (Camera, [Shape]) In the first argument of `parse_text', namely `shape_parse' In a 'do' expression: (cam, sh) - parse_text shape_parse input I'm probably missing something silly. Any hint would be appreciated. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec and type (IO t) error
Mike Gunter wrote: I'd guess that let (cam, sh) = parse_text shape_parse input is what you want? (Completely untested ...) Yep. That did it. Thanks, Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building GUIs for Haskell programs
Dmitri Pissarenko wrote: My goal behind experimenting with Haskell-based GUIs is to determine whether UI development in Haskell is much better (for instance, simpler, testable, maintainable) than in an imperative language. You might also be interested in wxFruit... http://zoo.cs.yale.edu/classes/cs490/03-04b/bartholomew.robinson/ ...although still a research project, it takes a more functional approach to GUI's. Greg Buchholz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Some random newbie questions
Benjamin Pierce wrote:
* What are the relative advantages of Hugs and GHC, beyond the obvious (Hugs
is smaller and easier for people not named Simon to modify, while GHC is a
real compiler and has the most up-to-date hacks to the type checker)? Do
people generally use one or the other for everything, or are they similar
enough to use Hugs at some moments and GHC at others?
snip
* I wrote a little program for generating Sierpinkski Carpets, and was
astonished to find that it runs out of heap under Hugs (with standard
settings -- raising the heap size with -h leads to a happier result).
As one data point, I don't think SOEGraphics works with GHC or
recent versions of Hugs (http://www.haskell.org/soe/graphics.htm). I
also tried a modified version of your Sierpinkski carpet program
(changed to spit out a PostScript file, since I don't have SOEGraphics).
Hugs chokes without increasing the stack, while my copy of GHC 6.2.1 runs
the program below quite fine, even without enabling optimizations.
Greg Buchholz
--Floating point PostScript version of Sierpinkski Carpet
fillSquare x y s = putStr $ x1 ++ y2 ++
x1 ++ y1 ++
x2 ++ y1 ++
x2 ++ y2 ++ box\n
where
x1 = (show x)++
x2 = (show (x+s)) ++
y1 = (show y)++
y2 = (show (y+s)) ++
carpet x y s =
if s 1
then fillSquare x y s
else let s' = s / 3
in do carpet xys'
carpet (x+s') ys'
carpet (x+s'*2) ys'
carpet x(y+s') s'
carpet (x+s'*2) (y+s') s'
carpet x(y+s'*2) s'
carpet (x+s') (y+s'*2) s'
carpet (x+s'*2) (y+s'*2) s'
psPreamble = putStr $ %!PS-Adobe-2.0\n ++
/box\n ++
{ newpath moveto lineto lineto lineto closepath fill} ++
def\n 0.05 setlinewidth\n
main = do psPreamble
carpet 50 250 500
putStr showpage\n
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Non-technical Haskell question
Jason Bailey wrote: As well as a lack of decent online tutorials, examples, etc. If it wasn't for the book /Haskell: The Craft of Functional Programming/ I would be much farther back in my comprehension then I am now. Speaking of books, are there any intermediate/advanced Haskell books? Ones that aren't introduction to programming texts? If I own the Hudak book, is it worthwhile to also acquire the Thompson book? Here's an analogy from the perl universe. If the _School_of_Expression_ is to _Learning_Perl_ (the llama), what are the Haskell equivalents of _Programming_Perl_ (camel) and _Perl_Cookbook_ (ram)? I suppose I should stop being lazy and contribute to the Haskell version of the PLEAC project... http://pleac.sourceforge.net/ Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Processing of large files
Peter Simons wrote: Read and process the file in blocks: http://cryp.to/blockio/docs/tutorial.html On a related note, I've found the collection of papers below to be helpful in understanding different methods of handling files in Haskell. http://okmij.org/ftp/Computation/Computation.html#enumerator-stream Now that cursors and enumerators are inter-convertible, an implementor of a collection has a choice: which of the two interfaces to implement natively? We argue that he should offer the enumerator interface as the native one. The paper elaborates that enumerators are superior: in efficiency; in ease of programming; in more predictable resource utilization and avoidance of resource leaks. We present a design of the overall optimal collection traversal interface, which is based on a left-fold-like combinator with premature termination. Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Global Variables and IO initializers: A proposal and semantics
John Meacham wrote: I have put some thought, some time ago, into the 'global initializers' problem in haskell but for various reasons never wrote up my conclusions. I'm not really qualified to answer, but does anyone think that this paper might have a solution? http://www.eecs.harvard.edu/~ccshan/prepose/prepose.pdf The configurations problem is to propagate run-time preferences throughout a program, allowing multiple concurrent configuration sets to coexist safely under statically guaranteed separation. This problem is common in all software systems, but particularly acute in Haskell, where currently the most popular solution relies on unsafe operations and compiler pragmas. We solve the configurations problem in Haskell using only stable and widely implemented language features like the type-class system. In our approach, a term expression can refer to run-time configuration parameters as if they were compile-time constants in global scope. Besides supporting such intuitive term notation and statically guaranteeing separation, our solution also helps improve the program's performance by transparently dispatching to specialized code at run-time. We can propagate any type of configuration data---numbers, strings, IO actions, polymorphic functions, closures, and abstract data types. No previous approach to propagating configurations implicitly in any language provides the same static separation guarantees. Greg Buchholz ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Re: OCaml list sees abysmal Language Shootout results
Malcolm Wallace wrote: For instance, the shootout often requires that a task be carried out N times, to make the timings large enough to measure. In all the naive Haskell implementations of these tasks, Haskell wins by a mile. Why? Because the language quite reasonably says that if you multiply a matrix by itself N times, but only use the result of the last multiplication, well it is jolly well not going to bother computing the first (N-1) identical multiplications - what a waste of time! So is it fair to compare the default lazy Haskell solution with all the eager solutions out there that laboriously do all this unnecessary work? Apparently not, so we have gone to all kinds of trouble to slow the Haskell solution down, make it over-strict, do the work N times, and thereby have a fair performance test. Huh. Well, the shootout appears to have two types of tests. Each individual test is labeled as either being implemented in the Same Way or doing the Same Thing. I agree that the Same Way test are usually too synthetic and too geared toward measuring artifacts of imperative programming which aren't appropriate in Haskell. But there are also the Same Thing tests that are free to be coded in any style at all. And of the Same Thing tests, the largest slowdown in the GHC programs is caused by lazy I/O (I think using better I/O routines would fix Reverse a File and Statistical Moments). To get GHC to come out on top of the CRAPS Scorecard, we need to emphasize the Same Thing tests and downplay the Same Way tests as well as properly weighting lines of code vs. memory consumption and speed. Here's one way to do it... http://makeashorterlink.com/?O5BD42089 What we probably need to do is create some new tests which aren't as phony and convince the powers-that-be to drop some of the synthetic tests or convert them to Same Thing tests (I think the Sum a Column of Integers and Spell Checker would be good candidates to convert). Just for reference, here's a list of the Same Thing tests: Simple TCP/IP Server Matrix Multiplication Statistical Moments Process Instantiation Reverse A File Ring of Messages Count Lines/Words/Chars Word Frequency Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Purely Functional Data Structures [was: OCaml list sees abysmal...]
Robert Dockins wrote: BTW can you give some references to these known techniques? See also, Purely Functional Data Structures by Chris Okasaki for functional implementations of queues, dequeues, etc. www-2.cs.cmu.edu/~rwh/theses/okasaki.pdf Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Algebraic Collections [was: OCaml list sees abysmal...]
Robert Dockins wrote: Actually, I've been wondering about this. If my understanding is correct, Haskell lists are basicly singly-linked lists of cons cells (is that correct?) A simple (I think) thing to do would be to make the lists doubly-linked and circular. That would let us do nice things like have O(1) primops for reverse, tail, (++) and other things that access lists at the end. However, I'm still pretty new to FP in general, so I don't know if there are any theoretical reasons why something like this couldn't work. Obviously lazy and infinite lists add some wrinkles, but I think it could be worked through. BTW can you give some references to these known techniques? Don't know if this is exactly what you are looking for, but I found these articles quite interesting. http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/ http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/democratic/ Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
Keith Wansbrough wrote: I just saw this on the OCaml list (in a posting by Rafael 'Dido' Sevilla [EMAIL PROTECTED] in the Observations on OCaml vs. Haskell thread). I can't believe that a simple wc implementation should be 570 times slower in Haskell than OCaml - could someone investigate and fix the test? I've been looking at the other shootout results (with the hope of learning something about making haskell programs faster/less memory hungry) and I couldn't quite figure out why the Hashes, part II test comsumes so much memory ( http://shootout.alioth.debian.org/bench/hash2/ ). So I started to try heap profiling, and generated the following graphs for the different types of profiles... biography = http://sleepingsquirrel.org/haskell/hash2_b.ps retainer = http://sleepingsquirrel.org/haskell/hash2_r.ps closure = http://sleepingsquirrel.org/haskell/hash2_d.ps type = http://sleepingsquirrel.org/haskell/hash2_y.ps cost cntr = http://sleepingsquirrel.org/haskell/hash2_c.ps ...but I have a hard time figuring out how to prevent something like stg_ap_3_upd_info or void cells from consuming so much memory. Anyone have pointers on how to best use the profile information? I'm still trying to digest Heap Profiling for Space Efficiency http://portal.acm.org/citation.cfm?id=734156 Are there any other related papers out there? (Of course it might be the case that I need a FiniteMap tutorial) Here's the code in question... import System (getArgs) import Data.FiniteMap main = do [n] - getArgs let get fm k = lookupWithDefaultFM fm 0 k let keys = map (\x - foo_ ++ show x) [0..] let hash1 = listToFM $ zip keys [0..] let hash2 = listToFM $ zip keys (repeat 0) let update k fm = addToFM_C (+) fm k (get hash1 k) let res = foldr update hash2 (concat $ replicate (read n) keys) putStrLn $ unwords $ map show [get hash1 foo_1, get hash1 foo_, get res foo_1, get res foo_] Thanks, Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results]
Sam Mason wrote: You probably want some strictness annotations in there. . . Now we're getting somewhere. When I replace the tuples with my own (strict) data structure, it gets about 7.5 times faster than the original shootout example (or about 24 times faster than the version with tuples). I get another 2x speedup when I pass '+RTS -G1' to the executable. So the version below is about 15 times faster than the original using the 3MB data file from the shootout. (Now we're only about 40x slower than ocaml). Don't forget to turn on '-funbox-strict-fields' for an additional improvement. -- Compile with... -- ghc -O2 -ddump-simpl -fvia-c -funbox-strict-fields -o wc_fold2 wc_fold2.hs -- execute as... ./wc_fold2 +RTS -G1 input.txt import IO main = do file - getContents putStrLn $ show (foldl wc (St 0 0 0) file) data Stuple = St !Int !Int !Int deriving Show wc (St l w c) '\n' = St (l+1) w(c+1) wc (St l w c) ' ' = St l (w+1) (c+1) wc (St l w c) x = St lw(c+1) ...It still seems like it's using a lot of memory (or at least doing a lot of garbage collecting). But it it still vastly better than before. Is there any way to reduce this more? (60,000,000 bytes divided by 3,000,000 chars = 20 bytes per char). Here's the memory usage report... 61,387,752 bytes allocated in the heap 11,837,148 bytes copied during GC 99,780 bytes maximum residency (234 sample(s)) 234 collections in generation 0 ( 0.11s) 1 Mb total memory in use INIT time0.00s ( 0.00s elapsed) MUT time0.15s ( 0.15s elapsed) GCtime0.11s ( 0.14s elapsed) EXIT time0.00s ( 0.00s elapsed) Total time0.26s ( 0.29s elapsed) %GC time 42.3% (48.3% elapsed) Alloc rate409,251,680 bytes per MUT second Productivity 57.7% of total user, 51.7% of total elapsed Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
Malcolm Wallace wrote: Here are the results, in seconds, on my machine (2.4GHz x86/Linux) for the suggested input (N=500) from the shootout site. All Haskell versions were compiled with ghc-5.04.2 -O2. I thought I'd take a stab at timing a few of the examples with different compiler versions to see what difference that would make (ghc-6.2.1 vs. ghc-6.3.20040928). I compared Kevin Everets' version with the two Tomasz Zielonka versions. I ran the test with N=2500 (i.e. 2500 copies of the original file, which is what is apparently used in the shootout) on my AthlonXP 1600 under x86/Linux. 6.2.1 6.3.20040928 --- --- Kevin 3.615s 3.156s Kevin (+RTS -G1) 1.666s 1.405s Tomasz (pretty) 0.725s 0.481s Tomasz (fast) 0.403s 0.430s Interesting to see the speed increase going from 6.2.1 to 6.3 for Tomasz' pretty example. Anyone have an explaination for the 2x speed increase for running Kevin's version with '+RTS -G1'? (And for reference, here's the results on my machine for the perl and gcc versions of the test and gnu/wc) perl-5.8.4 0.535s gcc-3.4.2 0.102s gnu/wc 0.435s Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
Andrew Cheadle wrote: +RTS -Sstderr -RTS and +RTS -sstderr -RTS will probably indicate why. I'd be surprised if the amount of data copied for the semi-space collector isn't much less than for the generational. Ahh. Data copied with '-G1' = 58MB vs. 203MB without. For posterities sake, here are the numbers... With '-G1' --- 306,616,872 bytes allocated in the heap 58,844,344 bytes copied during GC 99,316 bytes maximum residency (1169 sample(s)) 1169 collections in generation 0 ( 0.62s) 1 Mb total memory in use INIT time0.00s ( 0.00s elapsed) MUT time0.68s ( 0.71s elapsed) GCtime0.62s ( 0.68s elapsed) EXIT time0.00s ( 0.00s elapsed) Total time1.30s ( 1.39s elapsed) %GC time 47.7% (48.9% elapsed) Alloc rate450,907,164 bytes per MUT second Productivity 52.3% of total user, 48.9% of total elapsed Without --- 306,616,872 bytes allocated in the heap 203,339,812 bytes copied during GC 109,088 bytes maximum residency (131 sample(s)) 1169 collections in generation 0 ( 2.22s) 131 collections in generation 1 ( 0.05s) 2 Mb total memory in use INIT time0.00s ( 0.00s elapsed) MUT time0.79s ( 0.92s elapsed) GCtime2.27s ( 2.23s elapsed) EXIT time0.00s ( 0.00s elapsed) Total time3.06s ( 3.15s elapsed) %GC time 74.2% (70.8% elapsed) Alloc rate388,122,622 bytes per MUT second Productivity 25.8% of total user, 25.1% of total elapsed Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OCaml list sees abysmal Language Shootout results
Georg Martius wrote: Some more general comment: The code for the shootout doesn't need to be extremly fast in my eyes, it needs to be elegant and reasonable at performance and memory consuptions (In this order). I don't want to say that Thomaszs solution is bad, but it is not a typical Haskell style application. If someone (not haskeller) looks at the implementation it should be very obvious and clear. It might also be nice if the code would run under the other haskell compliers like Hugs and nhc98 right out-of-the-box. Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] Monads in Perl
Hopefully this isn't too far off topic. In my quest for monad understanding, I decided that it would be helpful if I translated Haskell code examples into a language I had a better understanding of. I ended up choosing Perl, and I decided to write up an article with my findings, in the hope of helping other newbies. FWIW, you can read it at... http://sleepingsquirrel.org/monads/monads.html (every true haskell hacker has to write at least one monad tutorial right?) If anyone has any questions/comments/suggestions, I'd be interested in hearing them. Thanks, Greg Buchholz ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] for large x, log (x::Integer) :: Double
-- Inspired from Mr. Howard Oakley. Might not qualify as good, -- but with this function I get log10(x)=849.114419903382 main = do print(show(log10(x))) x = 1301427272151881160612765560226881966218101403436917787184856303672382623256898455416763978959067300249652773943715743032733292602624834984761739233232794619193611954735720284761058146899246632367008536008917989689207753444916851859069225960265439153213675452291231593014452347270238624064599385936823085594101937144705866411597403257188107243160465138552039367484067881179355426659501377394743411557958891296796968015047325823672783086783214986710043714270547671666903964025267795520158937805183611280026836733145529671590438773283635061353921824995082955541839719790928834530340719498354530821282866299962327922291308021419628714011758281176918848669320822757025713685194594340820628167258289460256867016896063334140640075708083581866297494610834545554864846306383014549439540479675828018496049574066533167553894586573246931377586176000 log10 :: Integer - Double log10 n = let i = length(show(n)) - 1 t = take 12 (show(n)) r = read(t) f = r / 10 ^ (length(t) - 1) in fromIntegral(i) + log(f)/log(10) --Greg Buchholz ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] Favorite/recommended math books
I was wondering if the Haskellers out there have any favorite math texts they recommend for someone hoping to improve their programming skills by learning more math. I'm thinking about something at the undergraduate level that you enjoyed reading. What about Mr. Haskell Curry's _Foundations of Mathematical Logic_? Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: newbie question regarding type declarations
On Fri, 31 Oct 2003, gangadhar npk wrote: hi, I am a newbie to Haskell. I am reading the tutorial by Hal Daume III. Regarding the function types which are an extension of lambda calculus, I was wondering if at all it is possible to write a type that would return two values as the output - something like a square function which would take a pair and return a pair. I tried this, but there are errors square :: (Num a, Num b) = (a ,b) square (x , y) = (x*x , y*y) How can I specify that the square functions output would be a pair ? I'm also a Haskell newb, but I believe Num is actually a class of types, not an actual type itself. So you can't sustitute it for the Integer type below... square :: (Integer, Integer) - (Integer, Integer) ...Instead you have to say... square :: (Num a, Num b) = (a,b) - (a,b) ...Note the use of both the big arrow (=) and the small arrow (-). This is the most general type you could make for this particular function and allows you to mix amd match arguments like... square(3, 4) square(3.14, 4) square(2.718, 6.022) etc. Greg Buchholz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
