[Haskell-cafe] ANNOUNCE: Haskell BOF on 29c3 in Hamburg, Germany
Hi everybody, we will be running a nano-hackathon on the CCC congress in Hamburg on Thursday, 2012-12-27, 5pm German time: https://events.ccc.de/congress/2012/wiki/Haskell_BOF Sorry for the short notice. If you would like to meet up later during the congress please drop us a line. cheers, matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Q] multiparam class undecidable types
Thanks Oleg, that was very helpful. i can work with that. read the rest of this if you are curious where your hints took me. you are right, I need to make the functional dependency explicit: | class Table t c | t -> c where | toLists :: t -> [[c]] | fromLists :: [[c]] -> t | | instance Table [[c]] c where | toLists = id | fromLists = id | | instance (Table t c, Show c) => Show t where | showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (head . head $ toLists t) this compiles, and 'show' prints the first cell of each table. i also understand now why i can't just print all of them: [[Int]] is one of the types where the instances overlap. | instance Show Int | instance Show a => Show [a] vs. | instance Table [[Int]] Int | instance (Table [[Int]] Int, Show Int) => Show [[Int]] the advanced overlap code you are referencing below is fascinating, but isn't it a different problem? i don't want to distinguish different the cases "Show c" and "Typeable c", but i want to use whatever instance of "Show c" is available to implement "Show t". i can't make your solution work for this, because one of the two overlapping instances (namely "Show a => Show [a]") is already provided by the surrounding code that i cannot outfit with the advanced overlap trick. or am i missing something here? i think what i will do is to instantiate all table types individually: | instance Show c => Show (SimpleTable c) where | showsPrec p t = showParen (p > 10) $ showString "FastTable " . | shows (toLists t) cheers, matthias On Wed, May 09, 2012 at 06:41:00AM -, o...@okmij.org wrote: > Date: 9 May 2012 06:41:00 - > From: o...@okmij.org > To: f...@etc-network.de > CC: haskell-cafe@haskell.org > Subject: Re: [Q] multiparam class undecidable types > > > > | instance (Table a c, Show c) => Show a where > > I would have thought that there is on overlap: the instance in my code > > above defines how to show a table if the cell is showable; > > No, the instance defines how to show values of any type; that type > must be an instance of Table. There is no `if' here: instances are > selected regardless of the context such as (Table a c, Show c) > above. The constraints in the context apply after the selection, not > during. > > Please see > ``Choosing a type-class instance based on the context'' > http://okmij.org/ftp/Haskell/TypeClass.html#class-based-overloading > > for the explanation and the solution to essentially the same problem. > > There are other problems with the instance: > > | instance (Table a c, Show c) => Show a where > > For example, there is no information for the type checker to determine > the type c. Presumably there could be instances > Table [[Int]] Int > Table [[Int]] Bool > So, when the a in (Table a c) is instantiated to [[Int]] > there could be two possibilities for c: Int and Bool. You can argue > that the type of the table uniquely determines the type of its > cells. You should tell the type checker of that, using functional > dependencies or associated types: > > class Table table where > type Cell table :: * > toLists :: table -> [[Cell table]] > > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [Q] multiparam class undecidable types - how to get this example to typecheck?
Hi everybody,
I am torturing the ghc type inference extensions, and I think i
managed to break something, either in ghc or (more likely) in my
brain:
| {-# language FlexibleInstances, MultiParamTypeClasses, UndecidableInstances
#-}
|
| module Main
| where
|
| class Table table cell where
| toLists :: table -> [[cell]]
| fromLists :: [[cell]] -> table
|
| instance Table [[cell]] cell where
| toLists = id
| fromLists = id
|
| -- why i am using a class (not relevant for my question) -
| -- data FastTable a = FastTable ...
| -- instance Table (FastTable a) a where ...
|
| instance (Table a c, Show c) => Show a where
| showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows
(toLists t)
ghc 7.0.3 sais:
| Overlapping instances for Show [[cell0]]
| arising from a use of `shows'
| Matching instances:
| instance Show a => Show [a] -- Defined in GHC.Show
| instance (Table a c, Show c) => Show a
| -- Defined at /home/mf/tmp/z.hs:18:10-38
| In the second argument of `(.)', namely `shows (toLists t)'
I would have thought that there is on overlap: the instance in my code
above defines how to show a table if the cell is showable; the
(allegedly) overlapping instance defines how to show lists of alpha if
alpha is showable.
So I was expecting the reduction to go something like:
. table ~> [[cell]] (via whichever instance of class Table applies)
. [[cell]] ~> [cell] (via instance "Show a => Show [a]")
. [cell] ~> cell (via instance "Show a => Show [a]")
But it gets worse. I decided to ignore the problem for now and be
happy with at least showing the first cell in the upper left corner of
the table:
| instance (Table a c, Show c) => Show a where
| showsPrec p t = showParen (p > 10) $ showString "fromLists " . shows (head
. head $ toLists t)
to that, ghc 7.0.3 sais:
| /home/mf/tmp/z.hs:19:66:
| Context reduction stack overflow; size = 21
| Use -fcontext-stack=N to increase stack size to N
| $dShow :: Show c19
| $dShow :: Show c18
| [...]
shouldn't type inference be able to determine that
| ((head . head $ toLists t) :: c
and use the instance guaranteed by the instance declaration's class
constraint (Show c)?
I suspect that there should be a type annotation that would make this
approach possible, but even then I am curious what this behavior
means.
Should I upgrade to a more grown-up release of ghc?
Any hints or pointers appreciated. (:
Thanks,
Cheers,
Matthias
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hong Kong Haskell hackathon - call for participation
Hi everybody, if you are in or around Hong Kong in May and want to play, please check out this: http://www.haskell.org/haskellwiki/HkHac2012 Otherwise, any wider circulation or suggestion of channels / university people / companies that I should invite directly is welcome. cheers, Matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: hacphi satellite in berlin july 29-31
yet another hackathon: in case you wanted to join the philadelphia haskell hackathon but decided it's too far away (or in case you happen to be anywhere near and think this is a great opportunity), please join us in berlin: http://haskell.org/haskellwiki/Hac_%CF%86#Berlin_satellite admission is free. we have limited seats, so don't wait too long! hope to see you there, cheers, matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] infinite lists
On Tue, Mar 27, 2007 at 08:02:18PM +1000, Matthew Brecknell wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Matthew Brecknell <[EMAIL PROTECTED]> > Date: Tue, 27 Mar 2007 20:02:18 +1000 > Subject: Re: [Haskell-cafe] infinite lists > > Matthias Fischmann: > > g = do > > n <- randomRIO (0,5) > > let l = replicate n '*' > > i | null l = [] > > | otherwise = join $ repeat l > > print (take 12 i) > > If you had written (cycle l) instead of (join $ repeat l), you would > have figured it out much quicker. :-) > > Prelude> cycle [] > *** Exception: Prelude.cycle: empty list good point. and now i am learning a new word. eek! :) thanks - m ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] infinite lists
hi, it just took me an eternity to undestand a bug in my code *after* i had narrowed it down to eight lines or so. and as these bugs go, i feel very good about having found it and have to share it. although it's probably not that exciting to anybody except me. (-: here is the bug, narrowed to four lines. a function that only sometimes terminates. f = do n <- randomRIO (0,5) let l = replicate n '*' i = join $ repeat l -- infinite extension print (take 12 i) how many seconds does it take you to shout "you idiot!"? :-) spoiler below. (what would have been your fix?) cheers, matthias === spoiler. the problem is that l is sometimes empty, and taking an element out of an infinite concatenation of empty lists takes even longer than understanding that that takes quite long. just deal with the empty-list case separately: g = do n <- randomRIO (0,5) let l = replicate n '*' i | null l = [] | otherwise = join $ repeat l print (take 12 i) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial application
On Thu, Jan 18, 2007 at 10:26:25AM +0100, [EMAIL PROTECTED] wrote: > To: haskell-cafe@haskell.org > From: [EMAIL PROTECTED] > Date: Thu, 18 Jan 2007 10:26:25 +0100 > Subject: [Haskell-cafe] Partial application > > Hello, > > could someone please give me an example of the "partial application" of the > following curried function: > > add' :: Int -> Int -> Int > add' a b = a + b > > Normally, add' 1 should work, but it doesn't. it does work for me: | *Main> add' 1 | | Top level: | No instance for (Show (Int -> Int)) | arising from use of `print' at Top level | Probable fix: add an instance declaration for (Show (Int -> Int)) | In a 'do' expression: print it perhaps you didn't understand the error message? it is not about the outcome itself, it just states that the output cannot be displayed. (Int -> Int) is a type that doesn't "show". hth, m ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Collection of objects?
i have cut-and-pasted the last few postings into the wiki: http://haskell.org/haskellwiki/Heterogenous_collections it'is very ad hoc, but i hope it helps those who bump into it a little. and it's easier to edit and improve than a mailing list thread. (-: matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Collection of objects?
this is not exactly what you are looking for, but it contains a link to HList: http://www.haskell.org/haskellwiki/Extensible_record and then there is the follow-up work to HList, an OO library written in Haskell: http://homepages.cwi.nl/~ralf/OOHaskell/ it's quite a challenging read if you just want to go ahead and use hetero-collections, but it should give you a lot of ideas and pointers. i think there are also less type-safe alternatives in at least ghc. is Data.Typeable an interesting thing to look at? hth, matthias On Fri, Nov 17, 2006 at 06:36:30PM +0100, Valentin Gjorgjioski wrote: > To: haskell-cafe@haskell.org > From: Valentin Gjorgjioski <[EMAIL PROTECTED]> > Date: Fri, 17 Nov 2006 18:36:30 +0100 > Subject: [Haskell-cafe] Collection of objects? > > Is some kind of collection of object with different types in Haskell > exist? Except the tuples, which have fixed length. > I find this > >* Tuples heterogeneous, lists homogeneous. >* Tuples have a fixed length, or at least their length is encoded in > their type. That is, two tuples with different lengths will have > different types. >* Tuples always finite. > > But I need something which is heterogeneous and non-fixed length. I'm > used do Java, and this switch to functional languages is very strange to > me. So, to be clear, I need something like LinkedList in java. > > Can you please help me or suggest me, what can I use in this case? > > Valentin > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Institute of Information Systems, Humboldt-Universitaet zu Berlin web: http://www.wiwi.hu-berlin.de/~fis/ e-mail: [EMAIL PROTECTED] tel: +49 30 2093-5742 fax: +49 30 2093-5741 office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging partial functions by the rules
On Wed, Nov 15, 2006 at 03:54:31PM +1100, Donald Bruce Stewart wrote: > To: glasgow-haskell-users@haskell.org > Cc: haskell-cafe@haskell.org > From: Donald Bruce Stewart <[EMAIL PROTECTED]> > Date: Wed, 15 Nov 2006 15:54:31 +1100 > Subject: [Haskell-cafe] Debugging partial functions by the rules > > So all this talk of locating head [] and fromJust failures got me > thinking: > > Couldn't we just use rewrite rules to rewrite *transparently* > all uses of fromJust to safeFromJust, tagging the call site > with a location? The problem with tagging the call site is that there has to be an explicit location somewhere in the code that is maximally meaningful for the user. I don't think that's the whole story. I have always been wondering why error shouldn't always return a call stack from the occurrance of fromJust up to the function I typed into ghci (or up to main, for that matter). I guess this is because the call tree is rewritten extensively before being evaluated, and the output wouldn't be so easy to match to the source code? But shouldn't the mapping of source tree to executable tree be bijective, at least in theory? How hard would it be to hack call stack output into ghc? -matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to design default implementations of type class methods?
i haven't thought this through, but a variant of your first option may be to factor out extendedGCD into a class PIDEXT that is a parent of PID (occurs in the context of the declaration of PID). this way both methods will be available in PID. advantages: the dependencies are a little more explicit cycles are easier to avoid. drawbacks: more complicated interface less flexibility in implementation also i think there was an issue with superclass constraints not being inferrable from explicit subclass constraints, leading to bulky type signatures all over the code that is using your classes. but perhaps this gives somebody a better idea? m. On Mon, Nov 06, 2006 at 06:34:07PM +0100, Henning Thielemann wrote: > To: Haskell Cafe > From: Henning Thielemann <[EMAIL PROTECTED]> > Date: Mon, 06 Nov 2006 18:34:07 +0100 (CET) > Subject: [Haskell-cafe] How to design default implementations of type class > methods? > > > I like to hear some opinions about how to implement class method defaults. > > Let's consider the following example: > I want to classify types which allow for computation of the greatest > common divisor. The greatest common divisor can be computed by Euclid's > algorithm in some cases (integers, univariate polynomials) but not in all > cases (integer matrices, multivariate polynomials). So maybe it's a good > idea to set the Euclidean algorithm as default implementation for the GCD > method. Say, I have already implemented both the normal Euclidean > algorithm as "euclid", which only emits the GCD, and the extended > Euclidean algorithm "extendedEuclid" which also determines a and b in > "gcd(x,y) = a*x + b*y" for given x and y. > > Now I have two choices for implementing default methods: > > 1. Implement a method by calling other methods of the same class. > >class (Units a) => PID a where >extendedGCD :: a -> a -> (a,a,a) >extendedGCD = extendedEuclid divMod > >gcd :: a -> a -> a >gcd x y = let (g,_,_) = extendedGCD x y in g > >Advantage: User must implement only few methods, > here extendedGCD, the other ones work automatically. >Disadvantage: User must know, how the default methods call each other, > in order to not introduce cycles. > > 2. Implement a method by calling custom code, >preferably a public function according to > http://www.haskell.org/haskellwiki/Slim_instance_declaration > >class (Units a) => PID a where >extendedGCD :: a -> a -> (a,a,a) >extendedGCD = extendedEuclid divMod > >gcd :: a -> a -> a >gcd = euclid mod > >Advantages/Disadvantages are negated with respect to the first item. :-) > > > Ok, this example class is not well chosen, because in the case of > multivariate polynomials, not only extended Euclidean algorithm fails, but > it is in many cases not possible to represent the GCD of x and y as a > linear combination of x and y. > > My question is not limited to this case: I want to know, what reasons > exist pro and cons each alternative. Currently I prefer the first way, > because it reduces the work of implementing instances to the things that > are essential for the particular type. People who want specialized and > more efficient methods, must implement all methods. > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Institute of Information Systems, Humboldt-Universitaet zu Berlin web: http://www.wiwi.hu-berlin.de/~fis/ e-mail: [EMAIL PROTECTED] tel: +49 30 2093-5742 fax: +49 30 2093-5741 office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Module visibility of data type constructors
On Sat, Nov 04, 2006 at 09:39:39PM +0200, Slavomir Kaslev wrote: > To: haskell-cafe@haskell.org > From: Slavomir Kaslev <[EMAIL PROTECTED]> > Date: Sat, 4 Nov 2006 21:39:39 +0200 > Subject: [Haskell-cafe] Module visibility of data type constructors > > Hello. I have a simple question for data type constructors visibility. > Take a look: > > module Foo (Bar) where > data Bar = Bar > > In ghc this allows me to use Bar, the type constructor, in another > module, although it shouldn't be visible outside Foo. On the other > hand, if I change Bar's definition as: > > data Bar = Baz > > Baz isn't visible outside Foo. > > Is this the correct behavior or is it bug in ghc? It's not the correct behavior. The question is whether the bug is in your code or in ghc (with me it's usually the former :-). I can't reproduce this with my ghc 6.4. Which version are you using? Can you post the other module you are talking about? matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ruby quiz, Haskell wiki
On Thu, Oct 26, 2006 at 02:54:28PM +1000, Donald Bruce Stewart wrote: > To: haskell-cafe@haskell.org > From: Donald Bruce Stewart <[EMAIL PROTECTED]> > Date: Thu, 26 Oct 2006 14:54:28 +1000 > Subject: [Haskell-cafe] Ruby quiz, Haskell wiki > > I've created a page to document haskell solutions to the ruby quiz > puzzle series. > > http://haskell.org/haskellwiki/Haskell_Quiz thanks, i was meaning to do that. just added my code (and an extra intermediate page with a few more links). matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie and working with IO Int and Int
On Tue, Oct 17, 2006 at 01:21:38PM -0300, V?ctor A. Rodr?guez wrote: > To: haskell-cafe@haskell.org > From: "Víctor A. Rodríguez" <[EMAIL PROTECTED]> > Date: Tue, 17 Oct 2006 13:21:38 -0300 > Subject: [Haskell-cafe] Newbie and working with IO Int and Int > > Hi all, > > I'm really newbie to Haskell, and working on a program I'm trying to make > some testing. > I make some test on certain know values ( e.g. adding 10 to 15 must return > 25) and some test on random values (eg. adding rnd1 to rnd2 must return > rnd1+rnd2). > > The problem that makes me mad is the random number generation. I can obtain > random numbers through module Random but all of them return IO Int values > (all I need are Ints) instead of Int. > I know that I can adjust my own functions to use IO Int instead of Int but > the call to certain functions must contain Int parameters, because these > ones can't be changed to accept IO Int (I read > http://haskell.org/hawiki/ThatAnnoyingIoType and know that can convert from > IO Int to Int :-P). > > How can I deal with this problem ?? you should probably keep reading on. (-: have you seen the stuff on the new wiki? http://www.haskell.org/haskellwiki/Books_and_tutorials#Using_monads short answer: the type IO Int describes computations that yield integers, and in order to get to the Int you need to run the computation. if you have a pure function f and want to feed it with random values, you need to do something like: randomIO >>= \ x -> randomIO >>= \ y -> return (f x y) the complete expression has type IO Int again. don't try to strip off that IO; there are ways, but they don't teach you how to do it right. hth, m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] do ghci
On Wed, Oct 11, 2006 at 05:13:13PM -0700, Greg Fitzgerald wrote: > To: Haskell Cafe > From: Greg Fitzgerald <[EMAIL PROTECTED]> > Date: Wed, 11 Oct 2006 17:13:13 -0700 > Subject: [Haskell-cafe] do ghci > > Just curious, why does ghci run in the context of a 'do'? > > This tripped me up when I first started learning Haskell. It's fine once > you know what's going on, but why the restriction? Why can't I write the > code below without 'let' and ':module'? > > >two = 1 + 1 > >import Data.List > >cols = transpose [[1,2,3], [4,5,6]] If you interact with a command line, it is natural to have IO side effects and evaluate the command lines in the order of appearance. ghci is sort of a command line, right? It is straight-forward enough to make up something ad hoc without using the concept of monadic IO and memory modification, but why? matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Trying to understand HList / hSequence now [why it works]
On Tue, Oct 10, 2006 at 07:45:28PM -0700, [EMAIL PROTECTED] wrote: > To: [EMAIL PROTECTED] > Cc: haskell-cafe@haskell.org > From: [EMAIL PROTECTED] > Date: Tue, 10 Oct 2006 19:45:28 -0700 (PDT) > Subject: Re: Trying to understand HList / hSequence now [why it works] > > > Matthias Fischmann wrote: > > instance (Monad m, HSequence m HNil HNil) => HSequence m HNil HNil > > where hSequence _ = return HNil > > > > how can i use the goal of the declaration as one of the conditions > > without causing some sort of black hole in the type inference > > algorithm? > > Very easily: the instance head is implicitly the part of its own > context (so that a method can be recursive). A simple way to see that > is the following deliberately erroneous class: That explains why it is legal, but not why it can be necessary. In my code, I had to add the instance goal to the context in order for type inference to quite complaining about incomplete context. But never mind. I should really do some reading. Your hSequence implementation I like, yes. I will try that instead of mine, perhaps that'll soothen the type checker. thanks! matthias > > class C a where mc :: a -> Bool > > instance Eq a => C a where mc x = x > x > > The error message says > > Could not deduce (Ord a) from the context (C a, Eq a) > arising from use of `>' at /tmp/f2.hs:30:36 > > It is revealing to observe the context that the typechecker thinks is > available: it is (C a, Eq a). "Eq a" is there because we explicitly > wrote it in the instance declaration. C a is there just by default. We > could just as well written > > > instance (Ord a, C a) => C a where mc x = x > x > > Incidentally, the hSequence can be written as follows > > > import TypeCastGeneric2 > > data ConsM > > > > instance (TypeCast (m1 l) (m l), Monad m) > > => Apply ConsM (m a, m1 l) (m (HCons a l)) where > > apply _ (me,ml) = liftM2 HCons me (typeCast ml) > > > > hSequence l = hFoldr (undefined::ConsM) (return HNil) l > > > hlist = HCons (Just 1) (HCons (Just 'c') HNil) > > hlist2 = HCons ([1]) (HCons (['c']) HNil) > > testHSequence = hSequence hlist > > testHSequence2 = hSequence hlist2 > > *Foo> :t testHSequence > testHSequence :: Maybe (HCons Integer (HCons Char HNil)) > *Foo> testHSequence > Just (HCons 1 (HCons 'c' HNil)) > *Foo> testHSequence2 > [HCons 1 (HCons 'c' HNil)] > > The typechecker will complain if we try to mix different monads within > the same HList, and then sequence it. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginner's problem about lists
[start this post by reading the last paragraph, i just needed to go
through the rest to figure it out for myself.]
On Wed, Oct 11, 2006 at 03:14:23PM +0100, Malcolm Wallace wrote:
> To: haskell-cafe@haskell.org
> From: Malcolm Wallace <[EMAIL PROTECTED]>
> Date: Wed, 11 Oct 2006 15:14:23 +0100
> Subject: Re: [Haskell-cafe] beginner's problem about lists
>
> Matthias Fischmann <[EMAIL PROTECTED]> wrote:
>
> > > No, your Fin type can also hold infinite values.
> >
> > let q = FinCons 3 q in case q of FinCons i _ -> i ==> _|_
> >
> > does that contradict, or did i just not understand what you are
> > saying?
>
> That may be the result in ghc, but nhc98 gives the answer 3.
>
> It is not entirely clear which implementation is correct. The Language
> Report has little enough to say about strict components of data
> structures - a single paragraph in 4.2.1. It defines them in terms of
> the strict application operator ($!), thus ultimately in terms of seq,
> and as far as I can see, nhc98 is perfectly compliant here.
>
> The definition of seq is
> seq _|_ b = _|_
> seq a b = b, if a/= _|_
>
> In the circular expression
> let q = FinCons 3 q in q
> it is clear that the second component of the FinCons constructor is not
> _|_ (it has at least a FinCons constructor), and therefore it does not
> matter what its full unfolding is.
Interesting point. But one could argue that with strictness in data
types this is what happens:
FinCons 3 q
==> q `seq` FinCons 3 q
==> FinCons 3 q `seq` FinCons 3 q
==> q `seq` FinCons 3 q `seq` FinCons 3 q
==> ...
Section 4.2.1. of the H98 standard sais: "Whenever a data constructor
is applied, each argument to the constructor is evaluated if and only
if the corresponding type in the algebraic datatype declaration has a
strictness flag..." It is also reduced to strict function application
("$!") there, see Section 6.2. This yields:
FinCons 3 q (1.)
==> (\ x1 x2 -> ((FinCons $ x1) $! x2)) 3 q (2.)
==> (FinCons $ 3) $! q(3.)
==> q `seq` ((FinCons $ 3) q) (4.)
==> FinCons 3 q `seq` ((FinCons $ 3) q) (5.)
-- Hh. I suddenly see what you mean.
Ok, but isn't there a difference between "FinCons 3 q" as an
expression and "FinCons " as HNF? According to Section
4.2.1., the former is equivalent to a lambda expression in (2.), which
evaluates to (5.). So the first argument to seq in (5.) should
evaluate to (5.) as well, and so on.
Tell me I'm wrong, I want to learn something! (-:
thanks,
matthias
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginner's problem about lists
On Wed, Oct 11, 2006 at 11:40:59AM +0100, Malcolm Wallace wrote: > To: haskell-cafe@haskell.org > From: Malcolm Wallace <[EMAIL PROTECTED]> > Date: Wed, 11 Oct 2006 11:40:59 +0100 > Subject: Re: [Haskell-cafe] beginner's problem about lists > > ihope <[EMAIL PROTECTED]> wrote: > > > It's possible to make both "infinite list" and "finite list" > > datatypes: > > > > data Inf a = InfCons a (Inf a) > > data Fin a = FinCons a !(Fin a) | FinNil > > > > At least, I think the Fin type there has to be finite... > > No, your Fin type can also hold infinite values. The strictness > annotation on the (Fin a) component merely ensures that the tail exists > to one constructor's depth (Head Normal Form). It does not force > strictness all the way down (full Normal Form). let q = FinCons 3 q in case q of FinCons i _ -> i ==> _|_ does that contradict, or did i just not understand what you are saying? matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Profiling CAFs (re-post)
On Tue, Oct 10, 2006 at 01:59:23PM +0100, Ian Lynagh wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Ian Lynagh <[EMAIL PROTECTED]> > Date: Tue, 10 Oct 2006 13:59:23 +0100 > Subject: Re: [Haskell-cafe] Profiling CAFs (re-post) > > On Tue, Oct 10, 2006 at 01:31:58PM +0200, Matthias Fischmann wrote: > > > > What qualifies as constant applicable form, and why is it not > > labelled in a more informative way? > > CAFs are, AIUI, things that are just values (i.e. things that don't take > an argument) that have been floated up to the top level. Ok, this is consistent with the documentation. However, it doesn't explain why we would need to treat them differently. In particular, I don't understand why I wouldn't want to know their (module-global) names. > Compiling with -caf-all might give you more useful information. Oops. I thought i had that in my Makefile, but appearently i was wrong... If I add it, this is what happens: == module Main where x = f [1..5] (f [2..] [3..]) f xs ys = l where l = [ if s then x else y | (x, y) <- zip xs ys ] s = g xs ys g [] _ = True g _ [] = False g (x:xs) (y:ys) = g xs ys main = print (show x) == $ ghc -prof -caf-all Main.hs -o Main # (ghc 6.4) /tmp/ghc22775.hc:1475: error: redefinition of `Mainmain_CAF_cc_ccs' /tmp/ghc22775.hc:1470: error: `Mainmain_CAF_cc_ccs' previously defined here /tmp/ghc22775.hc:1490: error: redefinition of `Mainsat_CAF_cc_ccs' /tmp/ghc22775.hc:1480: error: `Mainsat_CAF_cc_ccs' previously defined here /tmp/ghc22775.hc:1495: error: redefinition of `Mainsat_CAF_cc_ccs' /tmp/ghc22775.hc:1490: error: `Mainsat_CAF_cc_ccs' previously defined here $ ghc -prof -auto-all -caf-all Main.hs -o Main /tmp/ghc22771.hc:1517: error: redefinition of `Mainmain_CAF_cc_ccs' /tmp/ghc22771.hc:1512: error: `Mainmain_CAF_cc_ccs' previously defined here > If that doesn't help then you might find it helpful to look at heap > profiles rather than just the normal profiler output. Section 5.4, prof.hp, yes. Probably should have thought of that myself. Will do. > > Why are there functions that inherit all of their (considerable) > > time and space consumption from elsewhere, but nothing in the > > list would allow for such a rich inheritage? > > I didn't understand that. If it's possible to give a small example then > that might help? Small is harder in this case than with type errors. But I'll try as soon as I know what's wrong with the above. thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [off-topic / administrative] List Reply-to
In my last post, I hit the wrong button again, with the effect of some noise in innocent mailboxes (sorry!). Some lists have the Reply-To: set to the list address. I think you can even configure the From: to be haskell-cafe instead of the poster, making the poster merely identifiable by the Sender: field. Do you have strong opinions on this subject? I would opt for setting Reply-To:; I think most of the follow-ups here are of some public interest, or easily filterable if not. cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginner's problem about lists
On Tue, Oct 10, 2006 at 08:58:05AM -0400, Lennart Augustsson wrote: > >a function that takes two lists and decides whether one of them is > >finite or not , without being given further information on the lists, > >does not exist. > > A function that takes two lists and decides if one is finite does > indeed exist. But if both are infinite you'll get partial > information out. > > The example > shorter [1..5] (shorter [2..] [3..]) > is a little tricky, but certainly doable. right, my implementation wouldn't cover this case. i was meaning termination, though: if a function accepts two possibly infinte lists, it cannot unconditionally return with the shorter one. i think the best you can do is Hennings solution (and mine, but i was too slow :) that hits bottom once you touch any element in (shorter [2..] [3..]), instead of merely the lengths of its prefices. matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginner's problem about lists
On Tue, Oct 10, 2006 at 08:10:44PM +0800, [EMAIL PROTECTED] wrote: > To: haskell-cafe@haskell.org > From: [EMAIL PROTECTED] > Date: Tue, 10 Oct 2006 20:10:44 +0800 > Subject: [Haskell-cafe] beginner's problem about lists > > Hi all, > > I'm trying to implement a function that returns the shorter one of two given > lists, > something like > shorter :: [a] -> [a] -> [a] > such that shorter [1..10] [1..5] returns [1..5], > and it's okay for shorter [1..5] [2..6] to return either. > > Simple, right? > > However, it becomes difficult when dealing with infinite lists, for example, > shorter [1..5] (shorter [2..] [3..]) > Could this evaluate to [1..5]? I haven't found a proper implementation. > > Again it's ok for shorter [2..] [3..] to return whatever that can solve > the above problem correctly. > An infinite list could work, I guess, but I don't know how. a function that takes two lists and decides whether one of them is finite or not , without being given further information on the lists, does not exist. you could add a third argument 'inifinity :: Int' that sets the minium length of all lists that are considered infinite. this is where your function could stop looking for an end in either of the two parameters: -- untested shorter infinity = reverse . f infinity [] [] f 0 ar al _ _ = ar f _ ar al [] _ = ar f _ ar al _ [] = al f (i+1) ar al (x:xs) (y:ys) = f i (x:ar) (y:al) xs ys or you could specify your function to be callable with at most one infinite list. i guess that's all you can do? matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Profiling CAFs (re-post)
Hi again, I posted a bunch of questions on profiling here a few days back, but couldn't tickle anybody to post a reply. Since I am not tired any more today, but still can't understand the documentation, or the output of the profiler, here it goes again: What qualifies as constant applicable form, and why is it not labelled in a more informative way? Why are there functions that inherit all of their (considerable) time and space consumption from elsewhere, but nothing in the list would allow for such a rich inheritage? As I said, I am happy to set up a wiki page if I learn anything that helps me improve the utility of profiling (the profiler and the rudimentary documentation are of great value as is). And i am happy to take pointers and go read articles if you tell me they help in the everyday work with ghc profiling. thanks / cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Trying to serialize HList
... and here is the code I am giving up on for today: Serialization of
HLists. Questions below.
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
module Foo where
import Char
import List
import Monad
import Permutation
import HListPrelude -- [1] http://web.engr.oregonstate.edu/~erwig/pfp/
-- Serializable is like Show, but
-- (a) it carries explicit type information, and
-- (b) it allows for serializing IORefs etc.
class Serializable s
where
serialize :: s -> IO String
deSerialize :: String -> IO s
instance Serializable Int where
serialize = return . ("Int::" ++) . show
deSerialize s | isPrefixOf "Int::" s = return . (read :: String -> Int) .
drop 5 $ s
instance Serializable Char where
serialize = return . ("Char::" ++) . show
deSerialize s | isPrefixOf "Char::" s = return . (read :: String -> Char) .
drop 6 $ s
-- SList is a list of heterogenous serializable elements...
class HList l => SList l
instance SList HNil
instance (Serializable s, SList ss) => SList (HCons s ss)
-- ... so it should be possible to write instantiate Serializable, right?:
instance (SList s, HMapOut Serialize s (IO String)) => Serializable s
where
serialize = liftM show . (sequence :: [IO String] -> IO [String]) . hMapOut
Serialize
deSerialize = error "Not yet. (I am not even done with serialize yet.)"
-- Seems we need the trick from the paper that oleg pointed out to me earlier
in this thread:
data Serialize = Serialize
instance (Serializable s) => Apply Serialize s (IO String) where apply _ =
serialize
-- Example:
slist = HCons (1 :: Int) (HCons ('c' :: Char) HNil)
test1 = serialize slist
-- (This is where -fallow-overlapping-instances helps. There is a
-- section in [1] on how to get rid of it, which I haven't read yet.)
test2 :: IO (HCons Int (HCons Char HNil))
test2 = test1 >>= deSerialize
Two questions:
(1) Do you see any reasons why it should be impossible in principle
to write deSerialize for the SList instance of Serializable? (I
think the answer is "it's possible to write it, but you need to
add quite some type information by hand".)
(2) The problem with test2 is that I need to know its precise
object-level type, ie which types occur at which positions in the
SList. I am pretty sure this is a restriction I have to live
with. Please tell me I am wrong. (-: (I think my application
will make it possible for ghc to infer the type, which is fixed
at compile time anyways, so it's not a severe restriction.)
(3) (bonus question :) Who wants to write deSerialize for SLists for
me?
And another one: Why do I need to list the HMapOut instance in the
context of the instance declaration of Serializable for SLists? (It's
not a big deal, but I can't see why it can't be inferred automatically
from the rest of the code.)
Possibly back with another issue of my HList diary tomorrow. (Please
tell me if you find this interesting or if you would like me to stop
being so verbose.)
cheers,
Matthias
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] collection monads
On Sun, Oct 08, 2006 at 10:57:46PM +1300, [EMAIL PROTECTED] wrote: > To: haskell-cafe@haskell.org > From: [EMAIL PROTECTED] > Date: Sun, 08 Oct 2006 22:57:46 +1300 > Subject: [Haskell-cafe] collection monads > > Matthias Fischmann wrote: > > > Do you expect the contained type x to change during a > > > sequence of monadic actions? e.g. would you ever use > (>>=) > > > at the type 'Permutation Int -> (Int -> Permutation > Bool) -> > > > Permutation Bool'? > > > > no, i don't need that. but aside from > > the fact that > > > > > data Permutation k v = > > > Permutation [(k, v)] > > > instance (Ix k) => > > > Monad (Permutation k) > > > > is redundant (i think of the permutation > > as a function applicable to arbitrary > > lists): how would that change anything? > > my definition of return still doesn't > > work. or how would you redefine > > 'return'? > > Ah. Yes, my approach falls over because it lacks two > things. #1: a distinguished value of the Ix-constrained > type k, to pair off with return's argument. #2: a purpose. > I don't have a clear idea of what a do-block in a > permutation monad ought to mean. Whoops! color=red>:-] yes, me neither. i thought of something like sequencial execution of permutations, and was hoping it was similar enough to strings and concat / join. but it seems it's something else... ok, permutations are not that monadic, really. i'll try to live with it. (-: matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Trying to understand HList / hSequence now (it works, but why?! :-0)
Hi,
here is how you do sequencing for HList, and a question why the type
signatures are valid. Here is the code:
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
module Foo where
import Char
import HListPrelude
class (Monad m, HList l) => HSequence m l l' | l -> m l'
where hSequence :: l -> m l'
instance (Monad m, HSequence m HNil HNil) => HSequence m HNil HNil
where hSequence _ = return HNil
instance (Monad m, HSequence m l l') => HSequence m (HCons (m a) l) (HCons a l')
where hSequence (HCons ma ml) = do
a <- ma
l <- hSequence ml
return (HCons a l)
hlist = HCons (Just 1) (HCons (Just 'c') HNil)
testHSequence = hSequence hlist
*Foo> testHSequence
Just (HCons 1 (HCons 'c' HNil)) :: Maybe (HCons Integer (HCons Char HNil))
what staggers me is the instance declaration of "HSequence m HNil
HNil": how can i use the goal of the declaration as one of the
conditions without causing some sort of black hole in the type
inference algorithm?
also i wanted to show off with the code :-). should i submit it
somewhere?
cheers,
matthias
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Trying to understand HList / hMapOut
thanks, to both of you!
"data Fooable" is the solution, and also very neat. it took me a
moment to learn the useful fact that a little explicit type
information can be worse than none, in particular with incomplete
contexts. but in the end it worked both without type signatures and
with the right ones.
cheers,
matthias
On Sat, Oct 07, 2006 at 12:25:07AM -0700, [EMAIL PROTECTED] wrote:
> To: [EMAIL PROTECTED]
> Cc: haskell-cafe@haskell.org
> From: [EMAIL PROTECTED]
> Date: Sat, 7 Oct 2006 00:25:07 -0700 (PDT)
> Subject: Trying to understand HList / hMapOut
>
>
> > I am using a heterogenous list as in [1] all elements of which are of
> > a given class C.
> > Since foo maps all class members to Int, hMapOut should be a
> > straight-forward way to produce homogenous Int lists from heterogenous
> > CLists:
> >
> > test :: (CList l) => l -> [Int]
> > test = hMapOut foo
>
> Well, `foo' is a polymorphic function -- which is not, strictly
> speaking, a first-class object in Haskell. Indeed, one cannot store
> polymorphic functions in data structures, unless one wraps them in a
> `newtype' or provide the explicit signature in some other way. In
> other words, higher-rank types become necessary.
>
> Fortunately, Haskell98 already has some rudimentary higher-ranked
> types (and multi-parameter type classes make them far more
> usable). So, even if Haskell had not had higher-ranked types, we
> could very easily get them from typeclasses, where they have been
> lurking all the time. In HList, the class Apply can be used to pry
> them out.
>
> Here's the complete code that seems to solve the original
> problem. There is no need to define the class CList.
>
> > {-# OPTIONS -fglasgow-exts #-}
> > {-# OPTIONS -fallow-undecidable-instances #-}
> >
> > module Foo where
> > import HListPrelude
> >
> > data T = T Int
> >
> > class C a where foo :: a -> Int
> > instance C T where foo (T i) = i
> >
> > data Fooable = Fooable
> > instance C a => Apply Fooable a Int where apply _ x = foo x
> >
> > test l = hMapOut Fooable l
> >
> > testc = test (HCons (T 1) (HCons (T 2) HNil))
>
> The inferred types are
>
> *Foo> :t test
> test :: (HMapOut Fooable r e) => r -> [e]
> *Foo> :t testc
> testc :: [Int]
>
> so no explicit signatures are needed.
--
Institute of Information Systems, Humboldt-Universitaet zu Berlin
web: http://www.wiwi.hu-berlin.de/~fis/
e-mail: [EMAIL PROTECTED]
tel: +49 30 2093-5742
fax: +49 30 2093-5741
office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany
pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Trying to understand HList / hMapOut
Hello, I am using a heterogenous list as in [1] all elements of which are of a given class C. I am awed by the beauty of the code (HList, not mine :-). Here is what I am trying doing: import HListPrelude data T = T Int class C a where foo :: a -> Int instance C T where foo (T i) = i class HList l => CList l instance CList HNil instance (C c, CList cs) => CList (HCons c cs) Since foo maps all class members to Int, hMapOut should be a straight-forward way to produce homogenous Int lists from heterogenous CLists: test :: (CList l) => l -> [Int] test = hMapOut foo That would be too easy, though... ghci (6.4) sez: /home/fis/tmp/Main.hs:16:7: Could not deduce (HMapOut (a -> Int) l Int) from the context (CList l) arising from use of `hMapOut' at /home/fis/tmp/Main.hs:16:7-13 Probable fix: add (HMapOut (a -> Int) l Int) to the type signature(s) for `test' or add an instance declaration for (HMapOut (a -> Int) l Int) In the definition of `test': test = hMapOut foo hugs (version 20050308) sez: ERROR "/home/fis/esim/HList/FakePrelude.hs":113 - Overlapping instances for class "Show" *** This instance : Show (HSucc a) *** Overlaps with : Show (HSucc HZero) *** Common instance : Show (HSucc HZero) (oops? should i upgrade, or is there a switch that i missed?) I am trying to understand the ghci error message, which looks like I might have missed a point. It seems like I should make it more obvious to ghc that CLists actually consist of values of type C. Is that a good guess? But how do I actually do it? I have unsuccessfully to extend the context to (HMapOut (a -> Int) l Int, CList l) or even to (C a, HMapOut (a -> Int) l Int, CList l) and I can't see any reason why the instance declarations of HMap in HListPrelude shouldn't cover my code. I am feeling a little stuck again... thanks, Matthias [1] http://homepages.cwi.nl/~ralf/HList/ signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] collection monads
On Thu, Oct 05, 2006 at 10:34:19AM +1300, [EMAIL PROTECTED] wrote: > To: haskell-cafe@haskell.org, [EMAIL PROTECTED] > From: [EMAIL PROTECTED] > Date: Thu, 05 Oct 2006 10:34:19 +1300 > Subject: [Haskell-cafe] collection monads > > Matthias Fischmann wrote: > > another beginners question about monads: given the type > > > > | data (Ix x) => Permutation x = Permutation [x] > > > > i wanted to define > > > > | instance Monad Permutation where > > | return xs = Permutation xs > > > > but of course nothing about the monad class guarantees xs to be of > > type list. the monad class seems unsuitable for holding collections, > > and i am inclined to not instantiate permutations. > > > > just to be sure: is there any easy way to do it that i missed? > > Do you expect the contained type x to change during a > sequence of monadic actions? e.g. would you ever use (>>=) > at the type 'Permutation Int -> (Int -> Permutation Bool) -> > Permutation Bool'? no, i don't need that. but aside from the fact that > data Permutation k v = Permutation [(k, v)] > instance (Ix k) => Monad (Permutation k) is redundant (i think of the permutation as a function applicable to arbitrary lists): how would that change anything? my definition of return still doesn't work. or how would you redefine 'return'? you gave me an idea, though: data Permutation a x = Permutation (Array x a -> Array x a) instance Monad (Permutation a) where return _ = Permutation id (>>=) (Permutation f) g = g f but this is dysfunctional for many reasons, too. for a start, (>>=) wouldn't really by good for anything, even if i could repair its type. composition of permutations seems to be something profoundly different from monadic binding. perhaps permutations just don't have it in them to become monads? matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] collection monads
another beginners question about monads: given the type | data (Ix x) => Permutation x = Permutation [x] i wanted to define | instance Monad Permutation where | return xs = Permutation xs but of course nothing about the monad class guarantees xs to be of type list. the monad class seems unsuitable for holding collections, and i am inclined to not instantiate permutations. just to be sure: is there any easy way to do it that i missed? thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] oddity with profiling
hi, i have been staring at a strange profile for a while now, and was wondering whether anybody could give me a hint. (using ghc.6.4. i know i should upgrade, but has the profiler changed after that in particular?) almost all time / memory costs occurs in a CAF cost center. as far as i understand, this means that the evaluation only takes place once each time i run the program, and doesn't depend on the input. Q1. why should one distinguish time spent in top-level constants from time spent in functions? (my program is basically a top-level constant that calls a function i am trying to understand with constant toy arguments.) curiously, the costs inherited by the CAF cost center and caused elsewhere do not show anywhere else, although i am pretty sure the call stack doesn't leave my code for another few levels. Q2. how can i learn which parts of my code causes the CAF cost centers to bloat? and what does it mean if the 100% inherited costs do not show in any other item in the cost center stack in my profile? user manual yields further confusion: | The cost of evaluating any expression in your program is attributed to | a cost-centre stack using the following rules: | | * If the expression is part of the one-off costs of evaluating the | enclosing top-level definition, then costs are attributed to the stack | of lexically enclosing SCC annotations on top of the special CAF | cost-centre. how can an expression be part of the one-off cost of anything? does the second part mean that the SCC annotations are on top of the special CAF cost-center? which is the special CAF cost-center? what does being on top of that mean? sorry, maybe i am just tired... :-/ | * Otherwise, costs are attributed to the stack of | lexically-enclosing SCC annotations, appended to the cost-centre stack | in effect at the call site of the current top-level | definition[7]. Notice that this is a recursive definition. | | * Time spent in foreign code (see Chapter 8, Foreign function | interface (FFI) ) is always attributed to the cost centre in force at | the Haskell call-site of the foreign function. thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cumulative sum
> try > scanl (+) 0 > for the cumulative sum and it is probably worth pointing out once more that (as i have learned only recently :-) Hoogle can help you even quicker than this list with questions like these: scanl is the fifth answer if you ask for a -> [a] -> [a]. also, the url is easy to remember: http://www.haskell.org/hoogle/ cheers, m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] question - which monad to use?
On Mon, Oct 02, 2006 at 11:42:22AM -0400, Tamas K Papp wrote: > To: haskell-cafe@haskell.org > From: Tamas K Papp <[EMAIL PROTECTED]> > Date: Mon, 2 Oct 2006 11:42:22 -0400 > Subject: Re: [Haskell-cafe] question - which monad to use? > > On Mon, Oct 02, 2006 at 11:35:40AM -0400, Tamas K Papp wrote: > > Matthias, > > > > Sorry if I was not clear in stating the problem. Your solution works no problem, i like to be confused by missing facts. (-: and you gave enough input for a discussion. > > type Failure = String > > data Computation a = Computation (Either Failure a) [a] > > > > instance Monad Computation where > > (Computation (Left e) h) >>= f = Computation (Left e) h -- do not > > proceed > > (Computation (Right a) h) >>= f = let r = f a -- result > > h' = case r of > > Left e -> h > > Right a' -> a':h > > in > > Computation r h' > > return (s,c) = Computation (Right (s,c)) [(s,c)] > > sorry, I pasted an older version. This line should be > > return a = Computation (Right a) [a] yeah, that works. the (>>=) part has two problems: (1) according to the Monad class, the type of f is (a -> m b), and the type of (a >>= f) is m b. but in your definition, (a >>= f) has the same type as a, no matter what f. (2) the cases in the definition of h' shouldn't be of type (Either Failure a), but of type (Computation b). the second one is easy to fix, just add the constructors to the case switches. the first is more of a conceptual problem: you want to have elements of potentially different types in the computation history h. this is unfortunate, given that you don't want make use of this flexibility of the class type, but i don't see a quick way around this. i have been meaning to read this for a while, perhaps that could help you (but i sense it's somewhat of an overkill in your case): Oleg Kiselyov, Ralf Laemmel, Keean Schupke: Strongly typed heterogeneous collections, http://homepages.cwi.nl/~ralf/HList/. donno... matthias > > Basically, I want the >>= operator to call f on the last result, if it > > is not a failure, and append the new result to the list (if it didn't > > fail). > > > > However, I am getting the following error message: > > > > /home/tpapp/doc/research/pricespread/Main.hs:62:58: > > Couldn't match the rigid variable `b' against the rigid variable `a' > > `b' is bound by the type signature for `>>=' > > `a' is bound by the type signature for `>>=' > > Expected type: [b] > > Inferred type: [a] > > In the second argument of `Computation', namely `h' > > In the definition of `>>=': > > >>= (Computation (Left e) h) f = Computation (Left e) h > > > > I don't know what the problem is. > > > > Thanks, > > > > Tamas > > > > On Mon, Oct 02, 2006 at 03:54:23PM +0200, Matthias Fischmann wrote: > > > > > hi, i don't fully understand your problem, but perhaps you could use > > > iterate to produce a list or type [Result a], ie, of all computation > > > steps, and then use this function to extract either result or error > > > from the list: > > > > > > > > > type Failmessage = Int > > > data Result a = Root a | Failure Failmessage deriving (Show) > > > > > > f :: [Result a] -> Either a (Int, [Result a]) > > > f cs = f [] cs > > > where > > > f (Root r:_) [] = Left r > > > f l [Failure i] = Right (i, reverse l) > > > f l (x:xs) = f (x:l) xs > > > > > > cs = [Root 1.2, Root 1.4, Root 1.38, Root 1.39121] > > > cs' = [Root 1.2, Root 1.4, Root 1.38, Failure 1] > > > > > > -- f cs ==> Left 1.39121 > > > -- f cs' ==> Right (1,[Root 1.2,Root 1.4,Root 1.38]) > > > > > > > > > (although this way you probably have the list still floating around > > > somewhere if you process the error returned by f, so f should probably > > > just drop the traversed part of the list.) > > > > > > hth, > > > matthias > > > > > > > > > > > > On Sun, Oct 01, 2006 at 06:00:43PM -0400, Tamas K Papp wrote: > > > > To: Ha
Re: [Haskell-cafe] question - which monad to use?
hi, i don't fully understand your problem, but perhaps you could use
iterate to produce a list or type [Result a], ie, of all computation
steps, and then use this function to extract either result or error
from the list:
type Failmessage = Int
data Result a = Root a | Failure Failmessage deriving (Show)
f :: [Result a] -> Either a (Int, [Result a])
f cs = f [] cs
where
f (Root r:_) [] = Left r
f l [Failure i] = Right (i, reverse l)
f l (x:xs) = f (x:l) xs
cs = [Root 1.2, Root 1.4, Root 1.38, Root 1.39121]
cs' = [Root 1.2, Root 1.4, Root 1.38, Failure 1]
-- f cs ==> Left 1.39121
-- f cs' ==> Right (1,[Root 1.2,Root 1.4,Root 1.38])
(although this way you probably have the list still floating around
somewhere if you process the error returned by f, so f should probably
just drop the traversed part of the list.)
hth,
matthias
On Sun, Oct 01, 2006 at 06:00:43PM -0400, Tamas K Papp wrote:
> To: Haskell Cafe
> From: Tamas K Papp <[EMAIL PROTECTED]>
> Date: Sun, 1 Oct 2006 18:00:43 -0400
> Subject: [Haskell-cafe] question - which monad to use?
>
> Hi,
>
> I have a computation where a function is always applied to the
> previous result. However, this function may not return a value (it
> involves finding a root numerically, and there may be no zero on the
> interval). The whole problem has a parameter c0, and the function is
> also parametrized by the number of steps that have been taken
> previously.
>
> To make things concrete,
>
> type Failmessage = Int -- this might be something more complex
> data Result a = Root a | Failure Failmessage -- guess I could use Either too
>
> f :: Double -> Int -> Double 0 -> Result Double
> f c0 0 _ = c0
> f c0 j x = {- computation using x, parameters calculated from c0 and j -}
>
> Then
>
> c1 = f c0 0 c0
> c2 = f c0 1 c1
> c3 = f c0 2 c2
> ...
>
> up to cn.
>
> I would like to
>
> 1) stop the computation when a Failure occurs, and store that failure
>
> 2) keep track of intermediate results up to the point of failure, ie
> have a list [c1,c2,c3,...] at the end, which would go to cn in the
> ideal case of no failure.
>
> I think that a monad would be the cleanest way to do this. I think I
> could try writing one (it would be a good exercise, I haven't written
> a monad before). I would like to know if there is a predefined one
> which would work.
>
> Thank you,
>
> Tamas
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Institute of Information Systems, Humboldt-Universitaet zu Berlin
web: http://www.wiwi.hu-berlin.de/~fis/
e-mail: [EMAIL PROTECTED]
tel: +49 30 2093-5742
fax: +49 30 2093-5741
office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany
pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cutting long strings into lines
On Sat, Sep 30, 2006 at 08:51:40PM +0200, Udo Stenzel wrote:
> To: Matthias Fischmann <[EMAIL PROTECTED]>
> Cc: haskell-cafe@haskell.org
> From: Udo Stenzel <[EMAIL PROTECTED]>
> Date: Sat, 30 Sep 2006 20:51:40 +0200
> Subject: Re: [Haskell-cafe] cutting long strings into lines
>
> Matthias Fischmann wrote:
> > although this wasn't the original problem, i like it, too :). but now
> > i am stuck in finding an optimal implementation for lines.
>
> Isn't the obvious one good enough?
>
> lines [] = []
> lines s = go s
> where
> go [] = [[]]
> go ('\n':s) = [] : lines s
> go (c:s) = let (l:ls) = go s in (c:l):ls
thanks. good enough, yes. just not obvious to me... (-:
matthias
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cutting long strings into lines
On Sat, Sep 30, 2006 at 04:36:02PM +0100, Neil Mitchell wrote:
> (if you can't be bothered to do that, the answer is "lines" ;)
although this wasn't the original problem, i like it, too :). but now
i am stuck in finding an optimal implementation for lines. the
following implementation is slightly slower than the built-in
function, and i suspect this to stem from the occurrance of reverse
for each line:
cut1 :: String -> [String]
cut1 = f ""
where
f x "" = [reverse x]
f x ('\n':xs) = reverse x : f "" xs
f x (c:xs) = f (c:x) xs
i vaguely remember having seen a CPS trick here before, but all i can
come up with is the yet a little slower
cut2 :: String -> [String]
cut2 = f id
where
f k "" = [k ""]
f k ('\n':xs) = k "" : f id xs
f k (c:xs) = f k' xs where k' cs = k (c:cs)
also, i think both implementations are line-strict, that is, each line
is fully evaluated once touched in the first character.
is there a similar implementation, with CPS or not, that is lazy in
the lines and more efficient?
thanks,
matthias
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cutting long strings into lines
On Sat, Sep 30, 2006 at 11:54:19AM -0400, Mark T.B. Carroll wrote:
> module WordWrap (wrap) where
> import Data.Maybe
>
> options :: String -> [(String, String)]
>
> options [] = [("", "")]
>
> options (x:xs) =
> let rest = map (\(ys, zs) -> (x:ys, zs)) (options xs)
> in if x == ' ' then ("", xs) : rest else rest
>
> bestSplit :: Int -> String -> (String, String)
>
> bestSplit width string =
> last (head wraps : takeWhile ((<= width) . length . fst) (options string))
works better if you just skip the "head wraps" part. (and now i am
curious: what was it supposed to mean? how did it get there?)
> wrap :: Int -> String -> [String]
>
> wrap _ "" = []
>
> wrap width string =
> let (x, ys) = bestSplit width string
> in x : wrap width ys
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Java or C to Haskell
... and if you want to search strings not single characters: findmatch s t e = take m . drop n $ t where m' = length e (n, m) = f 0 s f i s | take m' s == e = (i, m') | null s = (0, 0) | otherwise = f (i+1) (tail s) findmatch "asdfasdf" "asdfxvdf" "fas" == "fxv" (this one skips equality checks before *and* after the match. feel free post the necessary modifications. :) matthias On Wed, Sep 20, 2006 at 02:22:29AM -0700, Carajillu wrote: > To: haskell-cafe@haskell.org > From: Carajillu <[EMAIL PROTECTED]> > Date: Wed, 20 Sep 2006 02:22:29 -0700 (PDT) > Subject: Re: [Haskell-cafe] Java or C to Haskell > > > Yes, they must be equal the whole way, I like this recursive solution :) > > Ketil Malde-3 wrote: > > > > Carajillu <[EMAIL PROTECTED]> writes: > > > >> compare function just compares the two lists and return true if they are > >> equal, or false if they are not. > > > >> find_match "4*h&a" "4*5&a" 'h' > returns '5' (5 matches with the h) > >> find_match "4*n&s" "4dhnn" "k" > returns '' (no match at all - lists > >> are different anyway) > > > > Must they be equal the whole way, or just up to the occurrence of the > > searched-for character? > > > > find_match (x:xs) (y:ys) c | x==c = Just y > > | x/=y = Nothing > > | True = find_match xs ys c > > find_match [] [] _ = Nothing > > > > Or, to check the whole list: > > > > find_match (x:xs) (y:ys) c | x==c && xs == ys = Just y > > | x/=y = Nothing > > | True = find_match xs ys c > > find_match [] [] _ = Nothing > > > > -k signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization problem
> >Magnus Jonsson <[EMAIL PROTECTED]> writes: > > > >>splitStreams::Ord a=>[(a,b)]->[(a,[b])] > > > >>>splitStreams [(3,x),(1,y),(3,z),(2,w)] > >>[(3,[x,z]),(1,[y]),(2,[w])] > > > > [...] > > > >>But is there any way to write it such that each element is touched > >>only once? Or at least an O(n*log(m)) algorithm? > > > >I guess it should be possible to use a quicksort-like algorithm, > >splitting the stream into three streams with keys less than, equal, > >and greater than the first element, and recurse on the less/equal > >streams? something like this, then? splitStreams :: Ord a => [(a, b)] -> [(a, [b])] splitStreams [] = [] splitStreams ((a, b) : t) = (a, b : bs) : splitStreams t' where (bs, t') = foldr f ([], []) t f z@(a', b') (bs, t') = if a' == a then (b' : bs, t') else (bs, z : t') (i guess i should use a strictness '!' for (xs, ys), but i am still running ghc-6.5, and i don't like the case constructions that much. does this bite me here? i didn't check, really.) who can tune this any further? cheers, m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] data structures question
On Wed, Aug 30, 2006 at 03:11:35PM +0200, Tamas K Papp wrote: > [...] > > The mathematical description of the problem is the following: assume > there is a function V(a,b,theta), where a and b can have two values, > High or Low, and theta is a number between zero and n (n is given). > The range of V is the real numbers. > > Then there is an algorithm (called value iteration, but that's not > important) that takes V and produces a function of the same type, > called V'. The algorithm uses a mapping that is not elementwise, ie > more than the corresponding values of V are needed to compute a > particular V'(a,b,theta) -- things like V(other a,b,theta) and > V(a,b,theta+1), where > > data State = Low | High > other :: State -> State > other High = Low > other Low = High > > Question 1: V can be represented as a 3-dimensional array, where the > first two indices are of type State, the third is Int (<= n). What > data structure do you suggest in Haskell to store V? Is there a > multidimensional array or something like this? There are: http://haskell.org/onlinereport/array.html (There are other implementations with destructive updates and a more comfortable API, but pure Haskell98 is probably the best thing to start with.) The trick is that Int is not the only index data type, but tuples of index data types are, too. Do this: | type Point = (State, State, Int) | type TypeV = Array State Double | | matrix :: TypeV | matrix = array bounds values |where |... > Let's call this structure TypeV. > > Question 2: I would like to write > > valueit :: TypeV -> TypeV > valueit V = mapondescartesproduct [Low,High] [Low,High] [0..n] mapV where > -- mapV would calculate the new V' using V > -- mapV :: State -> State -> Int -> Double I think Array.ixmap is pretty much doing what you want, with slightly different typing. hth? matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Last statement in 'do' must be an expression error.
On Thu, Aug 17, 2006 at 10:18:25AM +0200, Szymon Z??bkiewicz wrote:
> To: haskell-cafe@haskell.org
> From: Szymon Z??bkiewicz <[EMAIL PROTECTED]>
> Date: Thu, 17 Aug 2006 10:18:25 +0200
> Subject: [Haskell-cafe] Last statement in 'do' must be an expression error.
>
> Hi.
>
> When trying to compilke this code:
>
> {...}
> 8.if (a == 0) && (b == 0)
> 9. then do
> 10. nr1 <- read (prompt "enter 1. number: ")
> 11. nr2 <- read (prompt "enter 2. number: ")
each do block needs to evaluate to some value when performed. if you
have nothing to return, do something like "return ()". (note this
only works if the type checker is happy with it. possibly you need to
restructure parts of the code you didn't post, too.)
> 12. else do
> 13.let nr1 = a
> 14.nr2 = b
> {...}
>
> The compiler tells me thats there's an error on line 10:
> "The last statement in a 'do' construct mesy be an expression"
>
> Could you tell me how to change it so that the "declaration" of the
> first nr1 and nr2 is still in the "then" block.
what about this code (untested)?
do
nr1 <- if a == 0 then read (prompt ":") else return a
nr2 <- if b == 0 then read (prompt ":") else return b
...
hth,
m.
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why Not Haskell? (sidenote on licensing)
Udo, us: > mf: > > AFAIR this happened to SSH.com with the > > bigint code in ssh-v1.3 > > SSH included GMP, which was licensed under the GPL. Nothing "happened" > there, only the OpenSSH folks disliked the license and reimplemented > GMP. ... and had to fight an ugly battle over the question whether the reimplementation was legitimate reuse of ideas or code theft. I don't understand why you have to be so insulting. I was making a false claim because I didn't know better, but I don't consider that a good reason to claim everything I am saying is bullshit and start a bar fight. Anyway this is not only getting ugly but also way off topic. I'm out. cheers, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why Not Haskell? (sidenote on licensing)
On Mon, Aug 07, 2006 at 12:57:47PM +0100, Chris Kuklewicz wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > CC: haskell-cafe@haskell.org > From: Chris Kuklewicz <[EMAIL PROTECTED]> > Date: Mon, 07 Aug 2006 12:57:47 +0100 > Subject: Re: [Haskell-cafe] Why Not Haskell? (sidenote on licensing) > > There is a false statement that must be corrected, about NDA's. Sorry. Just learned something, thanks! > Matthias Fischmann wrote: > >On Sun, Aug 06, 2006 at 10:46:16AM +0100, Chris Kuklewicz wrote: > >>[...] > >> > >>The GPL only gets in the way if you put it there by choosing to derive > >>work from GPL code. Note that most commercial programs do not allow you > >>the choice of deriving your work from theirs at all. The GPL adds to > >>your free-as-in-freedom: you can derive work from others' GPL work and > >>you can > > > >GPL also brings about restrictions to freedom-in-speech that are > >rarely mentioned: Say you develop the code for a client to run her > >production facilities. This code contains sensitive information about > >the way the facilities work and must not fall into the hands of the > >client's competitors. But if GPL is stuck to any part of the code and > >manages to infect the rest, the client can make you sign as many NDAs > >as there can be. > > The GPL is not a disease that "infect"s. That is a metaphor made by people > who hate such licenses. The GPL does not blow in the window or from > someone's sneeze and get "stuck" to code. To introduce GPL derived code is > a choice made be the programmer. You can always choose not to derive from > GPL code, and you can always change your mind later and rewrite the derived > code so you can remove it. Talking about biological metaphors is > deliberately misleading. Sorry, I didn't mean to offend anybody, or be misleading. I like GPL, but I also like the disease metaphor (although is not as much being sneezed at as having sex with somebody :-). And it's really not as easy to control as you suggest: If you ever take in a single patch under the GPL, or even implement a new feature in an obvious way that has been implemented by somebody else under the GPL, you are in trouble. AFAIR this happened to SSH.com with the bigint code in ssh-v1.3, but if you contradict me now I have to take your word for it. (So please do! :) > http://www.gnu.org/licenses/gpl-faq.html : > > >Does the GPL allow me to distribute a modified or beta version under a > >nondisclosure agreement? > > > >No. The GPL says that anyone who receives a copy of your version > >from you has the right to redistribute copies (modified or not) of > >that version. It does not give you permission to distribute the > >work on any more restrictive basis. (In my example I was worried about *less* restrictive, but the subsequent points seem to cover that, too.) > >GPL/LGPL is interesting, LGPL v3 may turn into something cool or not. > >(I heard they have problems sorting out the above scenario, too, or > >something more tricky, I forgot.) But placing restrictions on how the > >code may be used has lead to surprising problems. BSD on the other > >hand is a safe bet. > > Note that there are many people who will not do work on a BSD project since > a company can just come along and take it. People are free to choose GPL > or BSD for their work and then other people are free to choose whether to > derive work from them. But if there was no GPL and the only choice was BSD > then much of the current GPL'd work would not exist. I tend to agree. Would be fun to have some empirical data to boost the accuracy of the 'much' part of this. cheers, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why Not Haskell? (sidenote on licensing)
On Sun, Aug 06, 2006 at 10:46:16AM +0100, Chris Kuklewicz wrote: > > [...] > > The GPL only gets in the way if you put it there by choosing to derive work > from GPL code. Note that most commercial programs do not allow you the > choice of deriving your work from theirs at all. The GPL adds to your > free-as-in-freedom: you can derive work from others' GPL work and you can GPL also brings about restrictions to freedom-in-speech that are rarely mentioned: Say you develop the code for a client to run her production facilities. This code contains sensitive information about the way the facilities work and must not fall into the hands of the client's competitors. But if GPL is stuck to any part of the code and manages to infect the rest, the client can make you sign as many NDAs as there can be. The GPL still entitles you to sell it. I'm sure there are other scenarios in which the restritions that GPL places on the developer are equally prohibitive. GPL/LGPL is interesting, LGPL v3 may turn into something cool or not. (I heard they have problems sorting out the above scenario, too, or something more tricky, I forgot.) But placing restrictions on how the code may be used has lead to surprising problems. BSD on the other hand is a safe bet. cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Variants of a recursive data structure
On Thu, Aug 03, 2006 at 12:51:01PM +0200, Klaus Ostermann wrote: > To: haskell-cafe@haskell.org > From: Klaus Ostermann <[EMAIL PROTECTED]> > Date: Thu, 3 Aug 2006 12:51:01 +0200 > Subject: [Haskell-cafe] Variants of a recursive data structure > > Hi all, > > I have a problem which is probably not a problem at all for Haskell experts, > but I am struggling with it nevertheless. > > I want to model the following situation. I have ASTs for a language in two > variatns: A "simple" form and a "labelled" form, e.g. > > data SimpleExp = Num Int | Add SimpleExp SimpleExp > > data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String > > I wonder what would be the best way to model this situation without > repeating the structure of the AST. if you don't need to enforce that an exp is either completely labelled or not at all, how about this?: data Exp = Num Int | Add Exp Exp | Label Exp String this allows you to attach labels wherever you want, at the cost of an extra case each time you take an expression apart, which can be done in a separate function: unlabel :: Exp -> Exp unlabel (Label e _) = unlabel e unlabel (Add e e') = Add (unlabel e) (unlabel e') > The icing on the cake would be if it would also be possible to have a > function > > unlabel :: LabeledExp -> Exp that function is almost identical to the one above. cheers, matthias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A program which never crashes (even when a function calls "error")
On Tue, Aug 01, 2006 at 08:52:06AM +0200, Stephane Bortzmeyer wrote: > To: haskell-cafe@haskell.org > From: Stephane Bortzmeyer <[EMAIL PROTECTED]> > Date: Tue, 1 Aug 2006 08:52:06 +0200 > Subject: [Haskell-cafe] A program which never crashes (even when a function > calls "error") > > [It is a philosophical question, not a practical programming problem.] > > I'm used, in imperative programming languages with exceptions (like > Python) to call any function without fear of stopping the program > because I can always catch the exceptions with things like (Python): > > while not over: >try: > code which may raise an exception... >except Exception e: > do something clever > > How to do it in Haskell? How can I call functions like Prelude.head > while being sure my program won't stop, even if I call head on an > empty list (thus calling "error")? in haskell98, you can't. if you cannot prove a list will always be non-empty, you should use pattern matching instead of head. one disadvantage of exceptions is that the byte code tends to be slow and ugly and hard to generate, in particular in pure lazy languages. but admittedly sometimes exceptions are cool. therefore ghc comes with a quite sophisticated and mature exception handling library. http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Exception.html looks a little different from python, but should do the trick. cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Parsec] Backtracking with try does not work for me?
On Mon, Jul 31, 2006 at 09:04:32AM +0200, Stephane Bortzmeyer wrote:
>
> minilang = do
>char 'a'
>try (optional (do {comma ; char 'b'}))
>optional (do {comma ; char 'c'})
>eof
>return "OK"
>
> parse error at (line 1, column 2):
> unexpected "c"
> expecting "b"
>
> Apparently, "try" was used (do note that the column number indicates
> that there was backtracking) but the parser still fails for
> "a,c". Why?
minilang = do
char 'a'
try b <|> (return '-')
optional c
eof
return "OK"
where
b = do { comma ; char 'b' }
c = do { comma ; char 'c' }
The (return 'x') is needed for type consistency. The (try) combinator
doesn't spare you the error, it merely resets the cursor on the input
stream. To catch the parse error, you need to name a throwaway
alternative.
cheers,
matthias
--
Institute of Information Systems, Humboldt-Universitaet zu Berlin
web: http://www.wiwi.hu-berlin.de/~fis/
e-mail: [EMAIL PROTECTED]
tel: +49 30 2093-5742
fax: +49 30 2093-5741
office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany
pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional programming for processing oflargeraster images
On Thu, Jun 22, 2006 at 09:22:34AM +0100, Simon Peyton-Jones wrote: > To: Brian Hulley <[EMAIL PROTECTED]>, Joel Reymont <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Simon Peyton-Jones <[EMAIL PROTECTED]> > Date: Thu, 22 Jun 2006 09:22:34 +0100 > Subject: RE: [Haskell-cafe] Re: Functional programming for processing > oflargeraster images > > http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/BangPatterns > > Bang patterns make it much more convenient to write a strict function. > E.g > f (x, !y) = ... > is strict both in the pair (of course) but also in the second component > of the pair, y. i am ecstatic to hear that :). if it really means that 'y' will be fully evaluated (not top level normal form, but whatsthenameforthis, in the way ocaml evaluates expressions), it's something i have been missing so much that i was thinking of switching back to a strict language again. will upgrade as soon as i can, thanks! m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
On Wed, May 10, 2006 at 02:00:20PM +0900, Deokhwan Kim wrote: > To: haskell-cafe@haskell.org > From: Deokhwan Kim <[EMAIL PROTECTED]> > Date: Wed, 10 May 2006 14:00:20 +0900 > Subject: [Haskell-cafe] The values of infinite lists > > Are the values of infinite lists _|_ (bottom)? > > In section 1.3, the Haskell 98 report said as follows: > > Errors in Haskell are semantically equivalent to _|_. Technically, > they are not distinguishable from nontermination, so the language > includes no mechanism for detecting or acting upon errors. type theoreticians talk like that ;-). this paragraph is more about the "error" function than about infinite data structures. it means that whenever you trigger an "error ..." line, you make the program non-terminating, just like if you try to access the last element of an infinite list. the program still *ends* with an error message (notifying you that it won't *terminate*) because it is nice and it knows you don't like to wait forever. (-: > Therefore, the value of the following infinity is _|_. Right? > > data Nat = Zero | Succ Nat > > infinity = Succ infinity same as with lists: as long as you don't get lost in an infinitely distant point in the data structure, you are fine: you can do this ghci> case infinity of Succ _ -> "not there yet."; Zero -> "the end." ghci> take 1000 [1..] actually one of the things that i still find most amazing about haskell is that i can express so many algorithms by starting from the declaration of an infinite data structure and then traversing a finite part of it. the king paper on graph algorithms in haskell has some nice examples on this, too. cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] casting numerical types
On Sun, Apr 02, 2006 at 10:53:02AM +0100, Malcolm Wallace wrote: > To: haskell-cafe@haskell.org > From: Malcolm Wallace <[EMAIL PROTECTED]> > Date: Sun, 2 Apr 2006 10:53:02 +0100 > Subject: Re: [Haskell-cafe] casting numerical types > > Matthias Fischmann <[EMAIL PROTECTED]> writes: > > >avg :: (FractionalOrIntegral a) => [a] -> a > >avg xs = sum (map fromFractionalOrIntegral xs) / (fromIntegral (length > > xs)) > > Your condition is probably too strong. For one thing, there is no need > to convert every element of the list being summed, just its result. Also, > does the final result need to be the same type as the elements? > > avg :: (Num a, Fractional b) => [a] -> b > avg xs = fromRational (sum xs % toInteger (length xs)) you are right, your version looks better, and i managed to make ghc eat these variants: avg' :: (RealFrac a, Fractional b) => [a] -> b avg' xs = fromRational (round (sum xs) % toInteger (length xs)) avg'' :: (RealFrac a, Fractional b) => a -> [a] -> b avg'' epsilon xs = fromRational ((1 % toInteger (length xs)) * approxRational (sum xs) epsilon) But the problem is that (%) requests integral types, and I do not want to round my input. Also, I have the same problem as above that Integral types are not RealFrac, so these do not accept [Int] as input. When I try yours, however, I get: Couldn't match the rigid variable `a' against `Integer' `a' is bound by the type signature for `avg' Expected type: a Inferred type: Integer In the application `toInteger (length xs)' In the second argument of `(%)', namely `toInteger (length xs)' So do I need 'toNum' now? m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] casting numerical types
Ok. I was hoping that there was a common ancestor of Integral and Fractional. Now I realize that I can be more precise about what I wanted: avg :: (FractionalOrIntegral a) => [a] -> a avg xs = sum (map fromFractionalOrIntegral xs) / (fromIntegral (length xs)) But although it there may be a sound type system supporting this it looks a little weird... thanks, matthias On Sat, Apr 01, 2006 at 06:10:48PM -0500, Cale Gibbard wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Cale Gibbard <[EMAIL PROTECTED]> > Date: Sat, 1 Apr 2006 18:10:48 -0500 > Subject: Re: [Haskell-cafe] casting numerical types > > Arbitrary numerical types don't support division. (They're rings, not > fields.) The > (Fractional a) => [a] -> a > type is the best you can do. > > - Cale > > On 01/04/06, Matthias Fischmann <[EMAIL PROTECTED]> wrote: > > > > > > hi all, > > > > this should be a quick one (for now I would be happy with a "that's > > impossible", just want to make sure I don't miss anything). I want to > > compute the average from a list of arbitrary numerical element type. > > I wanted to do this: > > > > avg :: (Num a) => [a] -> a > > avg xs = sum (map fromNum xs) / (fromIntegral (length xs)) > > > > but it doesn't compile. All I could get to work is this: > > > > avg :: (Fractional a) => [a] -> a > > avg xs = sum xs / (fromIntegral (length xs)) > > > > avgI :: (Integral a) => [a] -> Float > > avgI = avg . map fromIntegral > > > > The two function names for the same thing are tolerable, but not very > > elegant. Is there another option? > > > > Thanks, > > Matthias > > > > > > -BEGIN PGP SIGNATURE- > > Version: GnuPG v1.4.1 (GNU/Linux) > > > > iD8DBQFELsI5TXPx/Y0ym6oRAuQuAKDJzqus2beMm5WKfJBupPTesm6XcQCgjohh > > yKhGfl6Wv3t97ZGfBYTXKQM= > > =mmOH > > -END PGP SIGNATURE- > > > > > > ___ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > > -- Institute of Information Systems, Humboldt-Universitaet zu Berlin web: http://www.wiwi.hu-berlin.de/~fis/ e-mail: [EMAIL PROTECTED] tel: +49 30 2093-5742 fax: +49 30 2093-5741 office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] casting numerical types
hi all, this should be a quick one (for now I would be happy with a "that's impossible", just want to make sure I don't miss anything). I want to compute the average from a list of arbitrary numerical element type. I wanted to do this: avg :: (Num a) => [a] -> a avg xs = sum (map fromNum xs) / (fromIntegral (length xs)) but it doesn't compile. All I could get to work is this: avg :: (Fractional a) => [a] -> a avg xs = sum xs / (fromIntegral (length xs)) avgI :: (Integral a) => [a] -> Float avgI = avg . map fromIntegral The two function names for the same thing are tolerable, but not very elegant. Is there another option? Thanks, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type classes
see my discussion a few moments ago, in particular my posting http://www.haskell.org/pipermail/haskell-cafe/2006-March/014981.html as you by now already know from this thread, the link tells you that the only possible solution is to turn the two entries to be compared into something of the same type, which can only be done with another type class. i am using 'Show' for now and compare the strings, because it's really simple and i don't care about performance at this stage of the project. might bite me later, though. cheers, matthias On Mon, Mar 20, 2006 at 05:46:43PM +0300, Max Vasin wrote: > To: haskell-cafe@haskell.org > From: Max Vasin <[EMAIL PROTECTED]> > Date: Mon, 20 Mar 2006 17:46:43 +0300 > Subject: [Haskell-cafe] Type classes > > > Hi! > > I'm currently experimenting with a bibliography generation tool for > LaTeX. It will (if it will be finished) use BibTeX databases but > bibliography styles will be written in Haskell. I want styles to be > able to transform database entries into some style specific data type, > so I define > > > class DatabaseEntry e where > > entryLabel :: e -> String > > formatEntry:: e -> String > > compareEntries :: e -> e -> Ordering > > Then I define > > > data Entry = forall a. (DatabaseEntry a) => Entry a > > > instance DatabaseEntry Entry where > > entryLabel (Entry e) = entryLabel e > > formatEntry (Entry e) = formatEntry e > > How can I define compareEntries for this instance? > > -- > WBR, > Max Vasin. > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Institute of Information Systems, Humboldt-Universitaet zu Berlin web: http://www.wiwi.hu-berlin.de/~fis/ e-mail: [EMAIL PROTECTED] tel: +49 30 2093-5742 fax: +49 30 2093-5741 office: Spandauer Strasse 1, R.324, 10178 Berlin, Germany pgp: AD67 CF64 7BB4 3B9A 6F25 0996 4D73 F1FD 8D32 9BAA ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: how would this be done? type classes? existentialtypes?
On Fri, Mar 17, 2006 at 04:53:42PM +, Ben Rudiak-Gould wrote:
>
> Matthias Fischmann wrote:
> >and now it gets interesting: i need instances for Rs on Show, Read,
> >Eq, Ord. Show is very simple, but Read?
>
> I think you're right: it's impossible to implement Read for Rs in an
> extensible way, because there's no way to obtain the necessary Resource
> dictionary at runtime. I've wished in the past for a family of functions,
With all the suggestions on this list I figured something out that
compiles, though. It requires extension of the Read instance of Rx,
but that's ok because it is an issue local to the module. Here is the
code:
class (Show a, Read a) => Resource a where
rsName :: a -> String
rsAdvance :: a -> a
rsStarved :: a -> Bool
data Rs = forall a . (Resource a) => Rs a
instance Resource Rs where
rsName(Rs a) = rsName a
rsAdvance (Rs a) = Rs (rsAdvance a)
rsStarved (Rs a) = rsStarved a
instance Show Rs where
show (Rs r) = "Rs " ++ rsName r ++ " (" ++ show r ++ ")"
instance Read Rs where
readsPrec pred = readConstructor
where
readConstructor ('R':'s':' ':'"':s) = readResourceType "" s
readConstructor s = []
readResourceType acc ('"':' ':'(':s) = readResource (reverse acc) s
readResourceType acc (x:s) | isAlpha x = readResourceType (x:acc) s
readResourceType _ s = []
readResource "Rice" s =
case readsPrec 0 s of
[(r :: RsRice, s')] -> readClosingParen (Rs r) s'; _ -> []
readResource "CrudeOil" s =
case readsPrec 0 s of
[(r :: RsCrudeOil, s')] -> readClosingParen (Rs r) s'; _ -> []
readResource _ s = assert False (error "no instance.")
readClosingParen r (')':s) = case readsPrec pred s of rs -> (r, s) : rs
readClosingParen _ _ = []
(Is there a better way to match list prefixes? If I had read a paper
on monadic parsing or two, this might look more elegant, but it seems
to me to be sufficient for this simple application. Feel free to post
the true thing. :-)
I am more convinced yet that Eq and Ord are impossible: Which specific
resource type is hidden in the Rs constructor is, well: hidden. But
there is a dirty trick if you have enough time and memory to waste,
and it doesn't even require extention for each new instance:
instance Eq Rs where r == r' = show r == show r'
instance Ord Rs where compare r r' = compare (show r) (show r')
And here are the resource instances:
data RsRice = RsRice
{
rsRiceName :: String, -- an intuitive and descriptive name of the
resource
rsRiceProduction :: Int,
rsRiceConsumption :: Int,
rsRiceReserve :: Int-- available for consumption or trading
}
deriving (Show, Read, Eq, Ord)
instance Resource RsRice where
rsName _ = "Rice"
rsAdvance r = r { rsRiceReserve = rsRiceReserve r + rsRiceProduction r -
rsRiceConsumption r }
rsStarved = (== 0) . rsRiceReserve
rsReserve (RsRice _ _ _ res) = res
rsSpend = rsRiceTrade (-)
rsEarn = rsRiceTrade (+)
rsRiceTrade :: (Int -> Int -> Int) -> RsRice -> Int -> RsRice
rsRiceTrade (+) r amount = r { rsRiceReserve = rsRiceReserve r + amount }
data RsCrudeOil = RsCrudeOil
{
rsCrudeOilName :: String,
rsCrudeOilProduction :: Int,
rsCrudeOilConsumption :: Int,
rsCrudeOilReserve :: Int,
rsCrudeOilReserveSize :: Int -- any water unit above this number is
discarded immediately.
}
deriving (Show, Read, Eq, Ord)
instance Resource RsCrudeOil where
-- ...
Btw, I am tempted to implemente crude oil as an incremental extension
to rice, by adding a record field 'rice'. Would this increase the
number of indirections for basic operations on resources, or would ghc
be capable of optimizing that away entirely?
Thanks again to all, I am following the thread, even if I won't answer
any more.
m.
signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how would this be done? type classes? existential types?
Alexandra Silva <[EMAIL PROTECTED]> wrote: > http://homepages.cwi.nl/~ralf/HList/ this looks like it might address my problems with Read / Eq instantiation? will read. thanks again to everybody. m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how would this be done? type classes? existential types?
On Thu, Mar 16, 2006 at 12:40:00PM +, Chris Kuklewicz wrote: > (Why isn't it "resourceName :: String" ?) because i am too clumsy. (-: when i am trying this, ghc complains that the type of resourceName doesn't have any occurrance of 'a', and i feel that it must be harder for the type engine to figure things out if there isn't, so resourceName is still a mapping from resources to their names. did i miss anything? m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] how would this be done? type classes? existentialtypes?
yes, that helps. also thanks to lennart and chris, i think i got it working. ... and have more questions: is there any difference between these two? if they are equivalent, why the two different ways to say it? data X where X :: (Resource a) => a -> X data Y = forall a . (Resource a) => Y a and now it gets interesting: i need instances for Rs on Show, Read, Eq, Ord. Show is very simple, but Read? if i look at a string, it's already to late to decide which type is has, right? same problem with Eq: i could first check whether the rsNames match and if so, go ahead and compare the two resource class instances inside Rs. but the type system would never know whether this is safe or not. solution: add methods rsEq, rsOrd to the Resource class and use them to instantiate Eq, and Ord respectively. this is not pretty, but not particularly ugly either, and it works. but this still doesn't work for Read, right? m. On Thu, Mar 16, 2006 at 01:37:36PM +0100, Geest, G. van den wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]>, haskell-cafe@haskell.org > From: "Geest, G. van den" <[EMAIL PROTECTED]> > Date: Thu, 16 Mar 2006 13:37:36 +0100 > Subject: RE: [Haskell-cafe] how would this be done? type classes? > existentialtypes? > > Try using a GADT: > > data Rs where > Rs :: Resource a => a -> Rs > > class Resource a where > resourceName :: a -> String > > instance Resource String where > resourceName x = "String" > > instance Resource Int where > resourceName x = "Int" > > resName (Rs x) = resourceName x > > resNames = map resName > > test = resNames [Rs "Hi", Rs (1::Int) ] > > The most important observations is that when pattern matching on (Rs x) we > cannot make any assumptions about x, except using the class members of > Resource. > > We hope this will help you, > > Gerrit (and the rest of the ST-lab) > > > > > -Original Message- > From: [EMAIL PROTECTED] on behalf of Matthias Fischmann > Sent: Thu 3/16/2006 12:57 PM > To: haskell-cafe@haskell.org > Subject: [Haskell-cafe] how would this be done? type classes? > existentialtypes? > > > > hi, > > this is one of those situations that always make scheme and perl > hackers laugh at me: i have written a piece of code that is > intuitively clear, and now i am trying to turn it into something that > compiles. and here it goes. > > i have a type class that looks something like this: > > class Resource a where > resourceName :: a -> String > resourceAdvance :: a -> a > resourceStarved :: a -> Bool > resourceSpend :: a -> Int -> a > resourceEarn :: a -> Int -> a > > resource types are rice, crude oil, pizza, software code, and so on. > they all have a different internal structure and the same abstract > interface, that's why i have defined this type class. > > now i want to create a list of a type similar to > > [r1, r2, r3] :: (Resource a) => [a] > > but with r1 being pizza, r2 being crude oil, and so on. my first idea > was this: > > data Rs = forall a . (Resource a) => Rs a > unRs (Rs a) = a > rsName :: Rs -> String > rsName = resourceName . unRs > ... > > and then export Rs as an abstract data type. this would allow for > lists of type [Rs], which is exactly what i want. > > but what is the type of unRs? or better: can i make it type at all? > and isn't this solution a little redundant and verbose? should i do > it like in the example for existentially quantified types in the ghc > manual? > > http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html > > but wouldnt't the code become really messy? or should i do the type > class and instances, and then do Rs the existentially quantified way, > with all class methods arguments to the Rs constructor? or is there a > completely different way to do this (besides using scheme or perl :-)? > > > thanks, > matthias > > > > > -Original Message- > From: [EMAIL PROTECTED] on behalf of Matthias Fischmann > Sent: Thu 3/16/2006 12:57 PM > To: haskell-cafe@haskell.org > Subject: [Haskell-cafe] how would this be done? type classes? > existentialtypes? > > > > hi, > > this is one of those situations that always make scheme and perl > hackers laugh at me: i have written a piece of code that is > intuitively clear, and now i am trying to turn it into something that > compiles. and here it goes. > > i have a type class that looks something like this: > > class Resource a where &
[Haskell-cafe] how would this be done? type classes? existential types?
hi, this is one of those situations that always make scheme and perl hackers laugh at me: i have written a piece of code that is intuitively clear, and now i am trying to turn it into something that compiles. and here it goes. i have a type class that looks something like this: class Resource a where resourceName :: a -> String resourceAdvance :: a -> a resourceStarved :: a -> Bool resourceSpend :: a -> Int -> a resourceEarn :: a -> Int -> a resource types are rice, crude oil, pizza, software code, and so on. they all have a different internal structure and the same abstract interface, that's why i have defined this type class. now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) => [a] but with r1 being pizza, r2 being crude oil, and so on. my first idea was this: data Rs = forall a . (Resource a) => Rs a unRs (Rs a) = a rsName :: Rs -> String rsName = resourceName . unRs ... and then export Rs as an abstract data type. this would allow for lists of type [Rs], which is exactly what i want. but what is the type of unRs? or better: can i make it type at all? and isn't this solution a little redundant and verbose? should i do it like in the example for existentially quantified types in the ghc manual? http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html but wouldnt't the code become really messy? or should i do the type class and instances, and then do Rs the existentially quantified way, with all class methods arguments to the Rs constructor? or is there a completely different way to do this (besides using scheme or perl :-)? thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: MUA written in Haskell (was: Getting GHC to print "Done" when it's finished linking?)
On Wed, Mar 08, 2006 at 07:52:28PM -, Brian Hulley wrote: > To: Nils Anders Danielsson <[EMAIL PROTECTED]> > Cc: Haskell Cafe > From: Brian Hulley <[EMAIL PROTECTED]> > Date: Wed, 8 Mar 2006 19:52:28 - > Subject: [Haskell-cafe] Re: MUA written in Haskell (was: Getting GHC to > print "Done" when it's finished linking?) > > Nils Anders Danielsson wrote: > >On Tue, 07 Mar 2006, "Brian Hulley" <[EMAIL PROTECTED]> wrote: > > > > [...] > [...] > > 5) Ideally the scripting language would be Haskell. There is already stuff > in Language.Haskell.* for doing parsing but I can't find anything which > would allow you to compile and load functions into a running program. this would be cool, but i don't think it's very urgent. i would be perfectly happy with a config directory that is scanned for code every time i *recompile* my MUA. it's not gonna happen every day. and for those few people who like installshields and still want to plug in code that doesn't come with the distribution, the entire program could be shipped within ghci. i don't think this is a very resource-hungry application for modern hardware standards. nice wish list. corpus navigation is missing, though. a large topic, and i have lots of ideas too half-baked to put in writing. but you should give it a thought. m. ps: did anybody get the riot thing compiled with ghc-6.4? i have the feeling there are some changes in the packageing interface in one of the last ghc version shifts that bit me, and i was too distracted to figure it out. though i am really curious. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] trying to understand runProcess handles
On Fri, Mar 03, 2006 at 09:05:49AM -0800, Donn Cave wrote: > To: haskell-cafe@haskell.org > From: Donn Cave <[EMAIL PROTECTED]> > Date: Fri, 3 Mar 2006 09:05:49 -0800 (PST) > Subject: Re: [Haskell-cafe] trying to understand runProcess handles > > On Thu, 2 Mar 2006, Matthias Fischmann wrote: > ... > > The problem is that gnuplot terminates right away after it tries to > > read from stdin (I can see the shadow of a window appear and vanish > > immediately). I tried setFdOption, with no effect. Is this because > > the handles passed to runProcess are closed in the parent process, and > > therefore the pipe is teared down and useless? > > > > I don't think so: If I run 'find /' instead of gnuplot, the process > > happily starts and I can hGetLine from stdout. > > That doesn't necessarily disprove your hypothesis, since "find" doesn't > read input. You might try "tr" instead, for example. I don't see > anything about what you were doing that would be obviously different > from runProcessInteractive, but as long as you're making a pipe for > error output, you may as well read it and see if gnuplot has left > any clue to its problem there. that doesn't work -- all the handles are closed at least after the process has died. hard to tell whether the process dying caused the handles to close or whether the handles were closed already by then. m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] rounding errors with real numbers.
ok, now i am intimidated enough to give up. (-:. thanks for trying, though. m. On Fri, Mar 03, 2006 at 03:19:44PM +0100, Henning Thielemann wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > cc: haskell-cafe@haskell.org > From: Henning Thielemann <[EMAIL PROTECTED]> > Date: Fri, 3 Mar 2006 15:19:44 +0100 (MET) > Subject: Re: [Haskell-cafe] rounding errors with real numbers. > > > On Fri, 3 Mar 2006, Matthias Fischmann wrote: > > > 1 + epsilon - 1 == epsilon, which is zero except for a very small > > rounding error somewhere deep in the e-minus-somethings. how is the > > error getting worse than that, for which numbers? > > I meant the relative error. epsilon should be the result, but the computer > says 0, so the absolute error is epsilon and the relative error is 1, that > is the number of reliable digits in the mantissa of the result is 0. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] rounding errors with real numbers.
On Fri, Mar 03, 2006 at 01:29:06PM +0100, Henning Thielemann wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > cc: haskell-cafe@haskell.org > From: Henning Thielemann <[EMAIL PROTECTED]> > Date: Fri, 3 Mar 2006 13:29:06 +0100 (MET) > Subject: Re: [Haskell-cafe] rounding errors with real numbers. > > > On Thu, 2 Mar 2006, Matthias Fischmann wrote: > > > > cancellation happens for instance here: 1 + 1e-50 - 1 == 0 > > > > the function again (in the wasteful original form, for clarity). > > where do you think cancellation may take place? isn't what you call > > canellation a generic rounding error? > > Cancellation is a special kind of rounding error. Rounding errors appear > everywhere, in (*), sin, exp and so on, but cancellations only arise on > differences. They are especially bad, because as the example above shows, > even if all numbers are given in double precision in the computation > a+b-a, no digit of the result is correct, that is 100% rounding error! The > danger of cancellation is everywhere where you subtract numbers of similar > magnitude. 1 + epsilon - 1 == epsilon, which is zero except for a very small rounding error somewhere deep in the e-minus-somethings. how is the error getting worse than that, for which numbers? m. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] trying to understand runProcess handles
hi there, I am running some unix command. I just realized there is runInteractiveProcess in System.Process, so my problem is solved in practice: ++ showPlot :: String -> IO (Handle, Handle, Handle, ProcessHandle) showPlot file = runInteractiveProcess executable arguments wd env where executable = "/usr/bin/gnuplot" arguments= ["-geometry", "-19+3", file, "-"] wd = Nothing env = Nothing ++ But first I tried to create the handles myself with createPipe from System.Posix.IO, and I failed for a reasons that I have no clue how to learn to understand. This is what the code looked like: ++ showPlot :: String -> IO (ProcessHandle, Handle, Handle, Handle) showPlot file = do (stdinR, stdinW) <- createPipeHandles (stdoutR, stdoutW) <- createPipeHandles (stderrR, stderrW) <- createPipeHandles h <- runProcess executable arguments wd env (Just stdinR) (Just stdoutW) (Just stderr W) return (h, stdinW, stdoutR, stderrR) where executable = "/usr/bin/gnuplot" arguments= ["-geometry", "-19+3", file, "-"] wd = Nothing env = Nothing createPipeHandles :: IO (Handle, Handle) createPipeHandles = do (fR, fW) <- createPipe hR <- fdToHandle fR hW <- fdToHandle fW return (hR, hW) ++ The problem is that gnuplot terminates right away after it tries to read from stdin (I can see the shadow of a window appear and vanish immediately). I tried setFdOption, with no effect. Is this because the handles passed to runProcess are closed in the parent process, and therefore the pipe is teared down and useless? I don't think so: If I run 'find /' instead of gnuplot, the process happily starts and I can hGetLine from stdout. If you have any clue I'd love to learn. Anyway, as I said, it's really better to simply use runInteractiveProcess in this simple case. thanks, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] rounding errors with real numbers.
> cancellation happens for instance here: 1 + 1e-50 - 1 == 0 the function again (in the wasteful original form, for clarity). where do you think cancellation may take place? isn't what you call canellation a generic rounding error? ++ normInterval :: [Double] -> Double -> Double -> [Double] normInterval ps lower upper = repair (map (\ x -> (x - oldLower) * stretch + lower) ps) where oldLower = head ps oldUpper = last ps stretch = (upper - lower) / (oldUpper - oldLower) -- fix rounding error: repair [i] = [upper] repair (h:t) = h : repair t ++ > >>(x-oldLower)*a + (oldUpper-x)*b i got this into my head though. neat. thanks! i will rewrite the function right now. cheers, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] rounding errors with real numbers.
On Mon, Feb 27, 2006 at 03:11:35PM +0100, Henning Thielemann wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > cc: haskell-cafe@haskell.org > From: Henning Thielemann <[EMAIL PROTECTED]> > Date: Mon, 27 Feb 2006 15:11:35 +0100 (MET) > Subject: Re: [Haskell-cafe] rounding errors with real numbers. > > > On Sun, 26 Feb 2006, Matthias Fischmann wrote: > > >I think this is the well-known issue of using real numbers in decimal > >representation on a machine that thinks binary, but I don't know what > >to do with it, and some of you maybe do. > > > >I want to shift+stretch a list of doubles into a given interval. > >example: > > > >| x1 = [2, 3, 4, 5, 10] > >| y1 = normInterval x1 0 1 > >| => y1 = [0.0,0.125,0.25,0.375,1.0] > > > >The function that does this looks something like this: > > > >| normInterval :: [Double] -> Double -> Double -> [Double] > >| normInterval ps lower upper = map (\ x -> (x - oldLower) * stretch + > >lower) ps > > Is there --^ > a cancellation problem? what's a cancellation problem? > Maybe you should use a kind of convex combination, that is > > (x-oldLower)*a + (oldUpper-x)*b i don't quite understand this either. is 'x' an old element in my input list and your expression is the corresponding new element? then how does the resulting curve relate to the original one? does this keep the ratios between distances between elements in the list intact? (this is the property that i am interested in.) but it sounds intriguing. perhaps i should play with this a little and find out myself. thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [Solved] rounding errors with real numbers.
On Sun, Feb 26, 2006 at 01:00:54PM +, Chris Kuklewicz wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Chris Kuklewicz <[EMAIL PROTECTED]> > Date: Sun, 26 Feb 2006 13:00:54 + > Subject: Re: [Haskell-cafe] rounding errors with real numbers. > > Your solution works, but is slightly wasteful with (repair) traversing > the whole list again. Here is a slightly more efficient expression: > > -- Precondition: The first parameter (xs) is sorted (ascending) : > -- assert (all (zipWith (<=) (xs, tail xs))) > -- low' < high' > -- low < high > normInterval :: [Double] -> Double -> Double -> [Double] > normInterval xs low high = let low' = head xs; high' = last xs; >scale = (high-low)/(high'-low') >middle = init (tail xs) >in (low : [scale*(x-low')+low) | x > <-middle])++[high] hi chris, i like this code better, too. slightly better still, because of fewer typos: normInterval :: [Double] -> Double -> Double -> [Double] normInterval ps lower upper = assert check ([lower] ++ [ stretch * (p - oldLower) + lower | p <- middle ] ++ [upper]) where check = lower < upper && oldLower < oldUpper && (and (zipWith (<=) ps (tail ps))) oldLower = head ps oldUpper = last ps stretch = (upper - lower) / (oldUpper - oldLower) middle = init (tail ps) but then i'll just take this as the best solution. thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] rounding errors with real numbers.
hi, I think this is the well-known issue of using real numbers in decimal representation on a machine that thinks binary, but I don't know what to do with it, and some of you maybe do. I want to shift+stretch a list of doubles into a given interval. example: | x1 = [2, 3, 4, 5, 10] | y1 = normInterval x1 0 1 | => y1 = [0.0,0.125,0.25,0.375,1.0] The function that does this looks something like this: | normInterval :: [Double] -> Double -> Double -> [Double] | normInterval ps lower upper = map (\ x -> (x - oldLower) * stretch + lower) ps | where | oldLower = head ps | oldUpper = last ps | stretch = (upper - lower) / (oldUpper - oldLower) However, with bigger numbers I get rounding errors: | x2 = [0.0,1.9569471624266144e-3,5.870841487279843e-3,1.5655577299412915e-2,3.913894324853229e-2,9.393346379647749e-2,0.2191780821917808,0.5009784735812133,1.1272015655577299,2.504892367906066] | y2 = normInterval x2 0 1 | => y2 = [0.0,7.8125e-4,2.34375003e-3,6.25e-3,1.56250003e-2,3.7506e-2,8.751e-2,0.2,0.45007,0.] The solution that pops to my mind is very simple: | normInterval :: [Double] -> Double -> Double -> [Double] | normInterval ps lower upper = repair (map (\ x -> (x - oldLower) * stretch + lower) ps) | where | oldLower = head ps | oldUpper = last ps | stretch = (upper - lower) / (oldUpper - oldLower) | | -- fix rounding error: | repair [i] = [upper] | repair (h:t) = h : repair t It works, but it's ugly. Is there a better way to do this? Thanks, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] enforcing strictness on arbitrary subexpressions
Thanks Udo, that helped a lot. I added the link to haskell.org. I couldn't find a proper place to put it, so I added a page 'By topic' (still quite empty) linked from the main page. (I hope that wasn't against any rules I missed; if anybody objects please feel free to remove it.) cheers, matthias On Thu, Feb 16, 2006 at 01:10:14PM +0100, Udo Stenzel wrote: > To: Matthias Fischmann <[EMAIL PROTECTED]> > Cc: haskell-cafe@haskell.org > From: Udo Stenzel <[EMAIL PROTECTED]> > Date: Thu, 16 Feb 2006 13:10:14 +0100 > Subject: Re: [Haskell-cafe] enforcing strictness on arbitrary subexpressions > > Matthias Fischmann wrote: > > I want to force evaluation on an arbitrary expression. > > [...] > > > main :: IO () > > main = do > >hPutStr stdout veryLongString -- lazy > >veryLongString `seq` hPutStr stdout veryLongString -- still lazy? > >(StrictThingy veryLongString) `seq` hPutStr stdout veryLongString > > -- strict (or at least i hope it is) > > The last line is actually equivalent to the second. Strict data > constructors are defined in term of seq, and seq only forces the > evaluation of the outermost constructor. So after seq'ing a string, it > is either empty or has at least one element, but that element and the > whole tail are still unevaluated. You have to recurse into the string > to evaluate everything: > > > hPutStr stdout $ foldr seq veryLongString veryLongString > > There is no primitive to do this for arbitrary data types, but the > DeepSeq type class comes close. You can find DeepSeq and some more > hints on strict evaluation at > <http://users.aber.ac.uk/afc/stricthaskell.html>. > > > Udo. > -- > Today is the tomorrow you worried about yesterday. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] module for probability distributions
hei again, (-: I wrote a module for sampling arbitrary probability distribution, so far including normal (gaussian) and uniform. http://www.wiwi.hu-berlin.de/~fis/code/ For those who need something like this: feel free to take it, it's BSD. For those who feel like growing their karma: - There are a few questions in the code (marked with 'XXX'). - There are probably far better way to do this. I am eager to learn. - There is probably a better implementation out there already. Please point me to it. cheers, Matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] enforcing strictness on arbitrary subexpressions
hei, I want to force evaluation on an arbitrary expression. What I have found is only strict datatypes (the '!' thing), but not a strictness idiom for arbitrary subexpressions. (I want this for debugging mostly, so if there is a better way to unsafePerformIO something in one piece I would be happy with that, too.) ++ veryLongString = "..." data StrictThingy = StrictThingy ! String main :: IO () main = do hPutStr stdout veryLongString -- lazy veryLongString `seq` hPutStr stdout veryLongString -- still lazy? (StrictThingy veryLongString) `seq` hPutStr stdout veryLongString -- strict (or at least i hope it is) ++ Problem with the last line is that it doesn't work for arbitrary types, and it's kind of ugly. What I would like to have is something like: ++ hPutStr stdout ! veryLongString ++ but I guess it's not that easy? Sorry for asking without consulting the list archives, but I promise I'll add it to the faq in the wiki once i understood. (-: I am using ghci and ghc, latest ubuntu package, but I am happy to switch to new versions. thanks, matthias signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
