[Haskell-cafe] Singapore Functional Programmer Group First Meetup
Sorry for the late notice. We are organizing an informal meeting for the Functional Programmer Group in Singapore on 2 Nov 2009. Since this is the first meeting, the theme will be mainly 'meet and greet' and discuss our interests in functional programming languages. We have participants coming from both the industry and the academia. If you happen to be in Singapore and interested in sharing your experience and interests, please contact Kenny at luzhuomi_AT_gmail_DOT_com. Best Regards, Kenny Zhuo Ming Lu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
On 30/10/09 05:32, Rogan Creswick wrote:
On Thu, Oct 29, 2009 at 6:54 PM, Magicloud Magiclouds
magicloud.magiclo...@gmail.com wrote:
My concern here is about the data member inheriting. In OOP, when I
inherit a class, I also got the members of it. But in haskell, how to
inherit a data?
[..]
The point of that whole rant is that extending data-bearing classes isn't
necessarily a good idea, so before trying to find a way to do it with
haskell, it may be better to just encapsulate another data type, which is
trivial:
data InnerThing = A | B | C
data OuterThing = Outer { innerThing :: InnerThing, otherField :: Int }
IIRC James Gosling once said that if he were to design Java today he would
leave out classes. I suppose partly due to many of the issues with data
inheritance.
/M
--
Magnus Therning(OpenPGP: 0xAB4DFBA4)
magnus＠therning．org Jabber: magnus＠therning．org
http://therning.org/magnus identi.ca|twitter: magthe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finally tagless and ghc-extensions
In both, the JFP APLAS paper, the authors note that no fancy type extension are needed for this approach. But in almost every (Haskell) example that is a bit more involved the authors do make use of functional dependencies and / or type families. GADTs are also being used, although *not* in the syntax definition... Just to dispel the doubts, here is the Haskell98 version of the previously posted code CB.hs (tagless final interpreter for call-by-name, call-by-value and call-by-need lambda-calculus with integers and constants) http://okmij.org/ftp/Haskell/CB98.hs It may appear somewhat less convenient. How less convenient -- well, you decide. The code can be easily re-written in OCaml, which has no typeclasses, type families and other bleeding edge features. Talking about it here is probably not appropriate. (I wonder if someone has ever cross-posted to the Haskell and Caml lists). P.S. I'm still digesting the Finally Tagless approach from Oleg, Jacques and Chen. You probably mean Chung-chieh Shan, whose last name is Shan and the first name is Chung-chieh. http://en.wikipedia.org/wiki/Chinese_name ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
Magnus Therning wrote: IIRC James Gosling once said that if he were to design Java today he would leave out classes. I suppose partly due to many of the issues with data inheritance. This sounds interesting. Can you link us to an article, please? Thanks, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: How to fulfill the code-reuse destiny of OOP?
Magicloud Magiclouds wrote In OOP, when I inherit a class, I also got the members of it. But in haskell, how to inherit a data? Although any OOP system has by definition, objects, not all of them have classes. The best example of a classless (also called 1-level, or prototype-based) OO system is Self, which is still alive. An object is essentially a record of data members. An extended object (an object of an extended class, for a class-based OOP) is an extended record. They could be quite convenient: we can add a new field to an existing record without re-writing the complete declaration and re-using lots of the functions that dealt with the old records. The old code would just work on extended records, ignoring the added field. (I am simplifying a bit.) Lots has been written about extensible records in Haskell; some techniques (such as parameterizing a record type by a tail) have been rediscovered several times. Still a good survey of many various ways to implement extensible records in Haskell is Section 3 of http://homepages.cwi.nl/~ralf/OOHaskell/paper.pdf It is long, as everything else in that paper. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
On this subject, I think, any content inherit would lead to trouble somehow. But is that the reason that we should totally cut them loose? I mean the way of programming developing is easier making (writing), easier maintaining. In fact, I think this is a fork in front of me: Before any new thoughts/ideas of programming theroy came out, I have to choose between much less code (and in this case, better organized code/object structure. I mean the code level, not the bunch of documents come along.) and easier maintenance. Of course, I would be very glad if we could have better solution. On Fri, Oct 30, 2009 at 3:46 PM, Martijn van Steenbergen mart...@van.steenbergen.nl wrote: Magnus Therning wrote: IIRC James Gosling once said that if he were to design Java today he would leave out classes. I suppose partly due to many of the issues with data inheritance. This sounds interesting. Can you link us to an article, please? Thanks, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
2009/10/30 Martijn van Steenbergen mart...@van.steenbergen.nl: Magnus Therning wrote: IIRC James Gosling once said that if he were to design Java today he would leave out classes. I suppose partly due to many of the issues with data inheritance. This sounds interesting. Can you link us to an article, please? Thanks, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe http://peter.michaux.ca/articles/transitioning-from-java-classes-to-javascript-prototypes (Under Second Tactic) -- Deniz Dogan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
On Fri, Oct 30, 2009 at 7:46 AM, Martijn van Steenbergen mart...@van.steenbergen.nl wrote: Magnus Therning wrote: IIRC James Gosling once said that if he were to design Java today he would leave out classes. I suppose partly due to many of the issues with data inheritance. This sounds interesting. Can you link us to an article, please? I actually managed to find it again :-) http://www.javaworld.com/javaworld/jw-08-2003/jw-0801-toolbox.html It seems I was wrong in my assumption about data inheritance, implementation inheritance is just as evil. /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
Magnus == Magnus Therning mag...@therning.org writes: Magnus It seems I was wrong in my assumption about data Magnus inheritance, implementation inheritance is just as Magnus evil. Both are fine. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
The following is purely my own experience, I have no links to papers of clever people :) I think none of the inheritance techniques work perfectly. E.g. describing everything with OO interfaces (=a extensible record of function pointers) is also problematic IMHO, at least when you have side effects. The problem with an interface (with side effects) is that people using the interface tend to depend on the side effects that a particular implementation of that interface performs. So in order to describe the contract for implementers of an interface, one often has to go into great detail. Also in Haskell it is required that an implementers follows the contract when implementing a type class, e.g. when writing a monad, you must make sure it follows the monad laws. But at least in Haskell, this can be proven, while in OO, one has to hope that the side effects of an implementation won't cause weird behavior elsewhere. In practice, this seems to work, most of the time :) The evolution of industrial OO the way I see it, is strange. You start with assembler, in which it is obvious to extend records. Then comes C, which makes extending records hard to do without casting and macros. Then C++, which offers insane ways of extending them (virtual base classes, multiple inheritance, mixins using templates, ...). Then to make software components more loosely coupled and maintainable, Corba COM enters the picture, and you only use interfaces to communicate with other objects. Of course COM uses reference counting, so reusable components is actually just an illusion; in order to avoid memory leaks, you need to know how objects are connected, which depends on the implementation... In the meantime Java becomes a succes. Java is basically back to basics: it tries to address some of the flaws of complicated OO, has garbage collection, promises multi-platform caps, and it is very easy to understand, so people embrace it. Then C# comes along, which initially is almost the same as Java, except is has closures, but it evolves towards a functional language with side effects (even Haskell's FRP will be available in .NET 4.0, with the Rx framework!). Then to manage large and complicated software, things like dependency injection and inversion of control are introduced, and... we're basically back to COM in a sense, but now with garbage collection. So I have the impression that OO is running in circles, and every iteration tries to pick up some goodies of the previous one, but where will it end? Luckily humans seem to have the ability to get things done, whatever primitive or flawed tools we get. I guess the brain itself it the best programming language ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
2009/10/30 Peter Verswyvelen bugf...@gmail.com: The following is purely my own experience, I have no links to papers of clever people :) I think none of the inheritance techniques work perfectly. E.g. describing everything with OO interfaces (=a extensible record of function pointers) is also problematic IMHO, at least when you have side effects. The problem with an interface (with side effects) is that people using the interface tend to depend on the side effects that a particular implementation of that interface performs. So in order to describe the contract for implementers of an interface, one often has to go into great detail. Also in Haskell it is required that an implementers follows the contract when implementing a type class, e.g. when writing a monad, you must make sure it follows the monad laws. But at least in Haskell, this can be proven, while in OO, one has to hope that the side effects of an implementation won't cause weird behavior elsewhere. In practice, this seems to work, most of the time :) The evolution of industrial OO the way I see it, is strange. You start with assembler, in which it is obvious to extend records. Then comes C, which makes extending records hard to do without casting and macros. Then C++, which offers insane ways of extending them (virtual base classes, multiple inheritance, mixins using templates, ...). Then to make software components more loosely coupled and maintainable, Corba COM enters the picture, and you only use interfaces to communicate with other objects. Of course COM uses reference counting, so reusable components is actually just an illusion; in order to avoid memory leaks, you need to know how objects are connected, which depends on the implementation... In the meantime Java becomes a succes. Java is basically back to basics: it tries to address some of the flaws of complicated OO, has garbage collection, promises multi-platform caps, and it is very easy to understand, so people embrace it. Then C# comes along, which initially is almost the same as Java, except is has closures, but it evolves towards a functional language with side effects (even Haskell's FRP will be available in .NET 4.0, with the Rx framework!). Then to manage large and complicated software, things like dependency injection and inversion of control are introduced, and... we're basically back to COM in a sense, but now with garbage collection. So I have the impression that OO is running in circles, and every iteration tries to pick up some goodies of the previous one, but where will it end? Luckily humans seem to have the ability to get things done, whatever primitive or flawed tools we get. I guess the brain itself it the best programming language ;) Looking at this from a feedback circuit perspective, it seems like that industrial programming is just swinging back and forth between two extremes. It appears that at every step someone runs into the limitations of doing things one way and finds a way to orthogonally combine other designs together. For example, there's been alot of work on implementing other languages on top of Java, such as Jython, so different programming methods can be mixed into enterprise Java code. It all swings back and forth because more than one design and paradigm is needed and no single language can really support it all at once. -Yaakov Nemoy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Applicative but not Monad
Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Yes. ZipList. http://en.wikibooks.org/wiki/Haskell/Applicative_Functors 2009/10/30 Yusaku Hashimoto nonow...@gmail.com: Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) I'll provide an alternative though, Const a is an applicative, but not a monad. Bob On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov ekirpic...@gmail.comwrote: Yes. ZipList. http://en.wikibooks.org/wiki/Haskell/Applicative_Functors 2009/10/30 Yusaku Hashimoto nonow...@gmail.com: Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Upgrading an app from happstack 0.1 to happstack 0.3
Upgrading an app from happstack 0.1 to happstack 0.3? Save yourself a few minutes and read this first. http://blog.patch-tag.com/2009/10/30/migrating-from-happstack-0-1-to-happstack-0-3/ -- Need somewhere to put your code? http://patch-tag.com Want to build a webapp? http://happstack.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie tom.da...@gmail.com wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) IIRC, that doesn't satisfy the associativity law, particularly when you are joining a list of lists of different lengths. 2 minutes of experimenting failed to find me the counterexample though. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
On Fri, Oct 30, 2009 at 12:59 PM, Luke Palmer lrpal...@gmail.com wrote:
On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie tom.da...@gmail.com wrote:
Of note, there is a sensible monad instance for zip lists which I *think*
agrees with the Applicative one, I don't know why they're not monads:
instance Monad (ZipList a) where
return = Ziplist . return
join (ZipList []) = ZipList []
join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
IIRC, that doesn't satisfy the associativity law, particularly when
you are joining a list of lists of different lengths. 2 minutes of
experimenting failed to find me the counterexample though.
This works fine for infinite lists, since an infinite list is
equivalent to Nat - a.
With finite lists, this implementation hits problems with calling head
on empty lists. If I rewrite it to avoid that problem, the
associativity law fails.
tail' [] = []
tail' (_:as) = as
diag ((a:_):bs) = a : diag (map tail' bs)
diag _ = []
bind :: [Int] - (Int - [Int]) - [Int] -- monomorphic for QuickCheck
bind m f = diag (map f m)
Prelude Test.QuickCheck Test.QuickCheck.Function quickCheck $ \m
(Function _ f) (Function _ g) - bind (bind m f) g == bind m (\x -
bind (f x) g)
*** Failed! Falsifiable (after 16 tests and 23 shrinks):
[1,0]
{0 - [-13,0], 1 - [0]}
{-13 - [], 0 - [0,0]}
The left side is [0,0], the right side is [0].
--
Dave Menendez d...@zednenem.com
http://www.eyrie.org/~zednenem/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Thanks for fast replies! Examples you gave explain why all Applicatives are not Monads to me. And I tried to rewrite Bob's Monad instance for ZipList with (=). import Control.Applicative instance Monad ZipList where return = ZipList . return (ZipList []) = _ = ZipList [] (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = f) zlHead :: ZipList a - a zlHead (ZipList (a:_)) = a zlCons :: a - ZipList a - ZipList a zlCons a (ZipList as) = ZipList $ a:as zlTail :: ZipList a - ZipList a zlTail (ZipList (_:as)) = ZipList as I understand if this instance satisfies the laws, we can replace $ with `liftM` and * and `ap`. And I found a counterexample (correct me if I'm wrong). *Main Control.Monad getZipList $ (*) $ ZipList [1,2] * ZipList [3,4,5] [3,8] *Main Control.Monad getZipList $ (*) `liftM` ZipList [1,2] `ap` ZipList [3,4,5] [3,6] Cheers, -~nwn On Sat, Oct 31, 2009 at 2:06 AM, Tom Davie tom.da...@gmail.com wrote: On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer lrpal...@gmail.com wrote: On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie tom.da...@gmail.com wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) IIRC, that doesn't satisfy the associativity law, particularly when you are joining a list of lists of different lengths. 2 minutes of experimenting failed to find me the counterexample though. Cool, thanks Luke, that explains why this is available in Stream, but not in ZipList too. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer lrpal...@gmail.com wrote: On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie tom.da...@gmail.com wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) IIRC, that doesn't satisfy the associativity law, particularly when you are joining a list of lists of different lengths. 2 minutes of experimenting failed to find me the counterexample though. Cool, thanks Luke, that explains why this is available in Stream, but not in ZipList too. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto nonow...@gmail.com wrote: Thanks for fast replies! Examples you gave explain why all Applicatives are not Monads to me. And I tried to rewrite Bob's Monad instance for ZipList with (=). import Control.Applicative instance Monad ZipList where return = ZipList . return (ZipList []) = _ = ZipList [] (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = f) This is taking the first element of each list, but you need to take the nth element. Try (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = zlTail . f) -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Thank you for your correction. I tried your (=) and replaced return's definition with return = ZipList . repeat then as you said this works fine for infinite lists. Cheers, -~nwn On Sat, Oct 31, 2009 at 2:39 AM, David Menendez d...@zednenem.com wrote: On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto nonow...@gmail.com wrote: Thanks for fast replies! Examples you gave explain why all Applicatives are not Monads to me. And I tried to rewrite Bob's Monad instance for ZipList with (=). import Control.Applicative instance Monad ZipList where return = ZipList . return (ZipList []) = _ = ZipList [] (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = f) This is taking the first element of each list, but you need to take the nth element. Try (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = zlTail . f) -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] \Statically checked binomail heaps?
Maciej Kotowicz wrote:
I'm trying to implement a binomial heaps from okaski's book [1]
but as most it's possible to be statically checked for correctness of
definition.
How about this encoding in Haskell 98?
data Tree a t = Tree { root :: a, children :: t }
data Nest a t = Nest { head :: Tree a t, tail :: t }
where
- Tree a () is a binomial tree of order 0
- Tree a (Nest a ()) is a binomial tree of order 1
- Tree a (Nest a (Nest a ())) is a binomial tree of order 2. and so on
data Heap' a t
= Z'
| D0' (Heap' a (Nest a t))
| D1' (Heap' a (Nest a t)) (Tree a t)
With (Tree a t) representing a binomial tree of rank n,
- Heap' a t represents the list of binomial trees of rank = n in a heap
- Z' represents an empty list
- D0' xs represents a list /without/ a tree of rank n
- D1' xs x represents a list /with/ a tree of rank n, namely x.
Finally, define
type Heap a = Heap' a ()
This forces Heap to be a well-shaped binomial heap, up to the equality
D0' Z' = Z'.
The main difference to standard binomial heaps is the existence of the
D0' nodes which represent skipped ranks. This makes the type checking
much easier (no comparison of natural numbers is required). It also
makes rank calculations unecessary - the rank increases implicitely as
the heap is traversed.
Heap order can be maintained by using a smart constructor:
-- combine two binomial trees of rank n into one of rank n+1
mkTree' :: Ord a = Tree a t - Tree a t - Tree a (Nest a t)
mkTree' l@(Tree a x) r@(Tree b y)
| a b = Tree a (Nest r x)
| True = Tree b (Nest l y)
Here is insert, as an example of a non-trivial operation:
insert' :: Ord a = Heap' a t - Tree a t - Heap' a t
insert' Z'b = D1' Z' b
insert' (D0' x) b = D1' x b
insert' (D1' x a) b = D0' (x `insert'` mkTree' a b)
HTH,
Bertram
P.S. As a refinement, one can define
data Heap a = Z | D0 | D1 (Heap' a a) a
This improves memory efficiency at the cost of requiring more code, like
mkTree :: Ord a = a - a - Tree a a
mkTree a b | a b = Tree a b
| True = Tree b a
insert :: Ord a = Heap a - a - Heap a
insert Zb = D1 Z' b
insert (D0 x) b = D1 x b
insert (D1 x a) b = D0 (x `insert'` mkTree a b)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Can you elaborate on why Const is not a monad? return x = Const x fmap f (Const x) = Const (f x) join (Const (Const x)) = Const x What am I missing? Tom Davie wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) I'll provide an alternative though, Const a is an applicative, but not a monad. Bob On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov ekirpic...@gmail.com mailto:ekirpic...@gmail.com wrote: Yes. ZipList. http://en.wikibooks.org/wiki/Haskell/Applicative_Functors 2009/10/30 Yusaku Hashimoto nonow...@gmail.com mailto:nonow...@gmail.com: Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru http://market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
What type is your return? On 30 Oct 2009, at 21:48, Dan Weston wrote: Can you elaborate on why Const is not a monad? return x = Const x fmap f (Const x) = Const (f x) join (Const (Const x)) = Const x What am I missing? Tom Davie wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) I'll provide an alternative though, Const a is an applicative, but not a monad. Bob On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov ekirpic...@gmail.com mailto:ekirpic...@gmail.com wrote: Yes. ZipList. http://en.wikibooks.org/wiki/Haskell/Applicative_Functors 2009/10/30 Yusaku Hashimoto nonow...@gmail.com mailto:nonow...@gmail.com: Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru http://market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to fulfill the code-reuse destiny of OOP?
Rogan Creswick wrote: On Thu, Oct 29, 2009 at 6:54 PM, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: My concern here is about the data member inheriting. In OOP, when I inherit a class, I also got the members of it. But in haskell, how to inherit a data? In my experience (almost entirely with Java), it is usually a bad idea to inherit from a class in order to reuse data storage that the parent class provides. Encapsulation (or a decorator, if you prefer) is often a safer choice. ...otherwise phrased in OO circles as people over-use inheritance and under-use collaboration. That said, I'm sure I won't be the first person here to say that generally, if you want to write a Haskell program, you should forget all about OOP and figure out how to structure it to make the best use of Haskell. It's a very different approach to program construction, and it requires a different way of thinking. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Yusaku Hashimoto wrote: Hello cafe, Do you know any data-type which is Applicative but not Monad? The Except datatype defined in the Applicative paper. Some parsers are not monads, allowing for optimizations. Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] uu-parsinglib pKeyword
Hi Ozgur, Ozgur Akgun wrote: pKeyword_Int = ( \ _ _ _ - int ) $ pSym 'i' * pSym 'n' * pSym 't' pKeyword_Float = ( \ _ _ _ _ _ - float ) $ pSym 'f' * pSym 'l' * pSym 'o' * pSym 'a' * pSym 't' As you can see there is an obvious pattern if you try to capture a keyword. If there were a function called pKeyword taking a string as an argument and producing the necessary parser, things would be easier. I think pToken in Text.ParserCombinators.UU.Derived does what you want. Groetjes, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Formlets are not Monads. http://www.haskell.org/haskellwiki/Formlets If you tried, you could actually implement a Monad instance for Formlets, but it would lead to very undesirable behavior. Specially, if a field in the form failed to validate, then the rest of the form would not be rendered at all. - jeremy On Oct 30, 2009, at 11:14 AM, Yusaku Hashimoto wrote: Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
If you use a monad instance for ZipLists as follows: instance Monad ZipList where return x = ZipList $ repeat x ZipList [] = _ = ZipList [] xs = f = diagonal $ fmap f xs (where diagonal pulls out the diagonal elements of a ziplist of ziplists) It will satisfy all the monad laws _except_ when the function f (in xs = f) returns ziplists of different length depending on the value passed to it. If f always returns lists of the same length, the monad laws should still hold even if the lists are not infinite in length. I have a fixed size list type (http://github.com/jvranish/FixedList) that uses an instance like this and it always satisfies the monad laws since the length of the list can be determined from the type so f is forced to always return the same size of list. I hope that helps things make sense :) - Job On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto nonow...@gmail.comwrote: Thanks for fast replies! Examples you gave explain why all Applicatives are not Monads to me. And I tried to rewrite Bob's Monad instance for ZipList with (=). import Control.Applicative instance Monad ZipList where return = ZipList . return (ZipList []) = _ = ZipList [] (ZipList (a:as)) = f = zlHead (f a) `zlCons` (ZipList as = f) zlHead :: ZipList a - a zlHead (ZipList (a:_)) = a zlCons :: a - ZipList a - ZipList a zlCons a (ZipList as) = ZipList $ a:as zlTail :: ZipList a - ZipList a zlTail (ZipList (_:as)) = ZipList as I understand if this instance satisfies the laws, we can replace $ with `liftM` and * and `ap`. And I found a counterexample (correct me if I'm wrong). *Main Control.Monad getZipList $ (*) $ ZipList [1,2] * ZipList [3,4,5] [3,8] *Main Control.Monad getZipList $ (*) `liftM` ZipList [1,2] `ap` ZipList [3,4,5] [3,6] Cheers, -~nwn On Sat, Oct 31, 2009 at 2:06 AM, Tom Davie tom.da...@gmail.com wrote: On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer lrpal...@gmail.com wrote: On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie tom.da...@gmail.com wrote: Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads: instance Monad (ZipList a) where return = Ziplist . return join (ZipList []) = ZipList [] join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as) IIRC, that doesn't satisfy the associativity law, particularly when you are joining a list of lists of different lengths. 2 minutes of experimenting failed to find me the counterexample though. Cool, thanks Luke, that explains why this is available in Stream, but not in ZipList too. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: dbus-core 0.5 and dbus-client 0.1
These are pure-Haskell client libraries for using the D-Bus protocol. D-Bus is heavily used for inter-application IPC on Free and open-source desktop platforms, such as Linux, OpenSolaris, and FreeBSD. These libraries allow applications written in Haskell to inter-operate with other components of recent GNOME, KDE, and XFCE desktops. This is the first real release of these libraries; dbus-core has been published on Hackage for some time, but mostly just to make sure I got the Cabal bits right. I feel they are now stable / featureful enough for public use. Both are available on Hackage: http://hackage.haskell.org/package/dbus-core http://hackage.haskell.org/package/dbus-client - dbus-core is an implementation of the D-Bus protocol, specifically the parts relevant to clients. Eventually, it will probably grow some functions useful for implementing a message bus as well. It includes type mapping / conversion, an implementation of the wire format (marshaling / unmarshaling), data types for the currently defined message types (METHOD_CALL, METHOD_RETURN, ERROR, and SIGNAL) and a basic parser / generator for introspection documents. It is roughly equivalent in purpose to libdbus. By itself, a protocol implementation is somewhat cumbersome to use, so dbus-client is a high-level wrapper. It provides some abstractions like remote object proxies, exported object trees, synchronous method calls, signal reception, and name reservation. Messages are received and processed in separate IO threads, allowing asynchronous method call and signal handling. The purpose between splitting the library into two packages is stability; dbus-core, ideally, will change only rarely -- performance improvements, new message / data types, etc. It provides a base level of functionality which more specialised libraries may use. dbus-client is an example of what such a library could look like, though for now it's not very Haskell-y (IO everywhere, exceptions, explicit locking). By separating the protocol from the client libs, alternative client libs can safely depend on the protocol implementation. - To see a sample of the library working, there's a clone of the dbus-monitor utility in dbus-core/Examples. Documentation is currently a bit lacking, so for now, the best documentation is the PDF of the source code itself, and the (rather barren) Haddock output: https://dl.getdropbox.com/u/1947532/dbus-core_0.5.pdf https://dl.getdropbox.com/u/1947532/dbus-core_0.5/index.html https://dl.getdropbox.com/u/1947532/dbus-client_0.1.pdf https://dl.getdropbox.com/u/1947532/dbus-client_0.1/index.html Once more people have used it without any major API issues, I'll write up a manual and populate the Haddock entries. Please respond with any feedback, difficulties, or suggestions. I'm particularly interested in ways to improve the public API, since I would rather make any breaking changes *before* anything big depends on these libraries. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
Some parsers are not monads, allowing for optimizations. Could you elaborate on them or give me some pointers? I think I heard about it two or three times, but I couldn't find any resource of them. -~nwn On Sat, Oct 31, 2009 at 5:35 AM, Martijn van Steenbergen mart...@van.steenbergen.nl wrote: Yusaku Hashimoto wrote: Hello cafe, Do you know any data-type which is Applicative but not Monad? The Except datatype defined in the Applicative paper. Some parsers are not monads, allowing for optimizations. Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative but not Monad
newtype Accy o a = Acc{acc :: o } -- Applicative Programming With Effects
Yusaku Hashimoto wrote:
Hello cafe,
Do you know any data-type which is Applicative but not Monad?
Cheers,
-~nwn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Tony Morris
http://tmorris.net/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Weekly News: Issue 137 - October 31, 2009
--- Haskell Weekly News http://sequence.complete.org/hwn/20091031 Issue 137 - October 31, 2009 --- Welcome to issue 137 of HWN, a newsletter covering developments in the [1]Haskell community. This week brings a new release of xmonad, some cool bindings to allow interaction with GNOME, KDE, and XFCE desktops and a new version of haskell-mode for the lesser of two editors... Some progress has also been made on the new HWN software, though this was mitigated by the fact that I started playing with the Isabelle theorem prover (after reading about Haskabelle) and so now I find myself convinced I should formally prove all of my software, and also that I'm pretty much incapable of getting things done when cool tools present themselves. In fact, I don't think I'll even be able to finish this [2]editori* [3]Exception: The Haskell Weekly News! Announcements xmonad 0.9 is now available! Don Stewart [4]announced a new version of everyone's favorite Tiling Window Manager, xmonad! The changes and improvments are too numerous to mention, see the post for details! WFLP2010 2nd CFP: LNCS + invited speaker + abstract due Nov 9. Pablo Nogueira [5]announced a second call for papers for the Workshop on Functional and Constraint Logic Programming. dbus-core 0.5 and dbus-client 0.1. John Millikin [6]announced pure-Haskell client libraries for using the D-Bus protocol. D-Bus is heavily used for inter-application IPC on Free and open-source desktop platforms, such as Linux, OpenSolaris, and FreeBSD. These libraries allow applications written in Haskell to inter-operate with other components of recent GNOME, KDE, and XFCE desktops. Singapore Functional Programmer Group First Meetup. Kenny Lu [7]announced (with apologies for the late notice) an informal meeting for the Functional Programmer Group in Singapore on 2 Nov 2009. The theme for the first meeting will be 'meet and greet'. GeBoP 1.7. Henk-Jan van Tuyl [8]updated and cabalized GeBoP (the General Boardgames Player) and uploaded it to hackage. GPS package on Hackage. Thomas DuBuisson [9]announced that he fixed up the GPS package to add correct distance calculation and a separate module for exporting KML. GPipe-TextureLoad 1.0.0 and GPipe 1.0.3. Tobias Bexelius [10]announced a new version of GPipe as well as a utility package for loading textures. HoleyMonoid-0.1. Martijn van Steenbergen [11]announced announce the first release of HoleyMonoid, a datatype that helps you build monoids with holes in them. The holes are filled in later using normal function application. GlomeVec, IcoGrid. Jim Snow [12]announced a couple of packages, GlomeVec is a vector library used in Jim's ray-tracer, and IcoGrid is a library for dealing with grids of hexagons and pentagons wrapped on a sphere. attempt-0.0.0. Michael Snoyman [13]announced a new package for exceptions haskell-mode 2.5. Svein Ove Aas [14]announced a new version of haskell-mode for that other 'editor'... Discussion Applicative but not Monad. Yusaku Hashimoto [15]asked about an example of a datatype that was an instance of Applicative, but not an instance of Monad. AND/OR Perceptron. Hector Guilarte [16]asked about how to understand a particular portion of JP Moresmau's [17]Perceptron in Haskell What is the current state of affairs with supercompilation? Eugene Kirpichov [18]asked about supercompilation in Haskell. Blog noise [19]Haskell news from the [20]blogosphere. Blog posts from people new to the Haskell community are marked with , be sure to welcome them! * Magnus Therning: [21]Playing with sockets in Haskell. * Holumbus: [22]Switched to Git. * Manuel M T Chakravarty: [23]Finally found the ghci bug on Snow Leopard. * Galois, Inc: [24]Tech Talk: Testing First-Order-Logic Axioms in AutoCert. * Brent Yorgey: [25]Collecting Attributes. * Darcs: [26]darcs weekly news #44. * FP Lunch: [27]Parser Combinators are as expressive as possible. * David Amos: [28]Simple groups, the atoms of symmetry. * Xmonad: [29]xmonad 0.9 available now!. * Michael Snoyman: [30]Introduction to attempt error reporting library. * FP-Syd: [31]Sydney FP Group: FP-Syd #20.. Quotes of the Week * hexpuem: [on learning haskell] the best way is to shove a SD card up your nose with learn yourself a haskell good on it * copumpkin: copumpkin: 'YOU ARE SUCH A PULLBACK' copumpkin: 'YOU KNOW WHAT? I FUNCTORED YOUR MOTHER LAST NIGHT' * saml and mauke: saml: 'How can I convert python file to haskell?' mauke: 'By piping it through a programmer' * monochrom: premature generality is the root of OOP * EvilTerran:
