Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: applicative instance (Graham Gill)
2. Re: Ambiguous type variable prevents the constraint `(Ord
t0)' from being solved. (鲍凯文)
3. Re: applicative instance (sasa bogicevic)
----------------------------------------------------------------------
Message: 1
Date: Mon, 30 Jan 2017 00:57:26 -0500
From: Graham Gill <[email protected]>
To: Haskell Beginners <[email protected]>
Subject: Re: [Haskell-beginners] applicative instance
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"; Format="flowed"
On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
> Is there a way to do it without defining a separate function like
> plusPlus ?
My guess is there isn't. I'm unsure what you mean by your question though.
Your List is a reimplementation of Haskell []. So, List with the
"Cartesian product" Applicative instance will, like Haskell [], extend
to a Monad instance. In the Monad instance for [], join = concat, and
the work of concat is done using ++.
For List, we can implement join using concatList:
concatList :: List (List a) -> List a
concatList Nil = Nil
concatList (Cons xs xss) = xs `plusPlus` (concatList xss)
and then we can add a Monad instance for List:
instance Monad List where
return = pure
xs >>= f = concatList (pure f <*> xs)
or equivalently, bind isgiven by
xs >>= f = concatList (fmap f xs)
To ask whether you can define the Cartesian product Applicative instance
for List without plusPlus, is, I think, like asking whether there is a
Cartesian product Applicative instance for List (or []) which doesn't
extend to a Monad instance. Because if it does extend to a Monad (that
obeys the Monad laws), then there will exist an implementation of join
:: List (List a) -> List a, and join will need to collapse a List of
Lists into a List. A function like plusPlus is used to accomplish the
collapse.
That's "proof by hand waving."
The Ziplist Applicative instance for List on the other hand can't be
extended to a Monad instance without additional restrictions on the
lengths of the lists. Your question led me to some interesting reading
with a google search on "list monad vs ziplist". Thanks.
On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
> Yep that worked, thanks.
> Is there a way to do it without defining a separate function like plusPlus ?
>
>
>
>
>
>> On Jan 28, 2017, at 10:43, Francesco Ariis<[email protected]> wrote:
>>
>> On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
>>> Ok so how would the implementation look to get the correct result ?
>>> I can't seem to write something that will compile except ZipList version.
>> One way is by implementing your own (++):
>>
>> data List a = Nil | Cons a (List a) deriving (Eq, Show)
>>
>> plusPlus :: List a -> List a -> List a
>> plusPlus Nil bs = bs
>> plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)
>>
>> instance Functor List where
>> fmap f Nil = Nil
>> fmap f (Cons a b) = Cons (f a) (fmap f b)
>>
>> instance Applicative List where
>> pure x = Cons x Nil
>> Nil <*> _ = Nil
>> _ <*> Nil = Nil
>> (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20170130/9a680355/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 30 Jan 2017 00:38:44 -0800
From: 鲍凯文 <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Ambiguous type variable prevents the
constraint `(Ord t0)' from being solved.
Message-ID:
<camjcg+gcau5s6m-sqnqcstso8hgbbi2fnsmjcfhxdq0op0q...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
I refactored it as such:
apply_listd [] d x = d x
apply_listd ((a,b):t) d x =
case compare x a of
EQ -> a
GT -> b
_ -> d x
applyd f d x = look f
where
k = 5
look (Leaf h l)
| h == k = apply_listd l d x
look (Branch p b l r)
| (k `xor` p) .&. (b - 1) == 0 = look (if k .&. b == 0 then l else r)
look _ = d x
...and it compiled so i'm not sure what happened there. Simpler though:
adding the type signature
applyd :: Ord a => Func a b -> (a -> b) -> a -> b
also made it compile. I'm not sure why ghc thinks there's multiple
instances to choose from (somebody please explain), but in any case adding
type signatures will give you better error messages/help ghc.
Hope that helps a bit.
On Sun, Jan 29, 2017 at 4:00 AM, <[email protected]> wrote:
> Send Beginners mailing list submissions to
> [email protected]
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> or, via email, send a message with subject or body 'help' to
> [email protected]
>
> You can reach the person managing the list at
> [email protected]
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Beginners digest..."
>
>
> Today's Topics:
>
> 1. Ambiguous type variable prevents the constraint `(Ord t0)'
> from being solved. (Ivan Kush)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sat, 28 Jan 2017 23:09:09 +0300
> From: Ivan Kush <[email protected]>
> To: [email protected]
> Subject: [Haskell-beginners] Ambiguous type variable prevents the
> constraint `(Ord t0)' from being solved.
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset=utf-8
>
> I get this error (full message at the end of the mail). How could I
> correct my code?
>
>
> ===================
> Code:
> ===================
>
> module Intro where
>
> import Data.Bits -- for xor, .&.
>
> data Func a b
> = Empty
> | Leaf Int [(a, b)]
> | Branch Int Int (Func a b) (Func a b)
>
> applyd =
> let apply_listd l d x =
> case l of
> [] -> d x
> (a, b) : t ->
> let c = compare x a
> in if c == EQ then b
> else if c == GT then apply_listd t d x
> else d x
>
> in \f d x ->
> let k = 5 -- hash x - todo
> in let look t =
> case t of
> Leaf h l | h == k ->
> apply_listd l d x
> Branch p b l r | (k `xor` p) .&. (b - 1) == 0 -> --
> (Branch p b l r) | ((k xor p) .&. (b - 1)) == 0 ->
> look (if k .&. b == 0 then l else r)
> _ -> d x
> in look f
>
>
>
> ===================
> Error:
> ===================
>
> Intro.hs:37:25: error:
> * Ambiguous type variable `t0' arising from a use of `apply_listd'
> prevents the constraint `(Ord t0)' from being solved.
> Relevant bindings include
> l :: [(t0, t)] (bound at Intro.hs:36:28)
> t :: Func t0 t (bound at Intro.hs:34:21)
> look :: Func t0 t -> t (bound at Intro.hs:34:16)
> x :: t0 (bound at Intro.hs:32:15)
> d :: t0 -> t (bound at Intro.hs:32:13)
> f :: Func t0 t (bound at Intro.hs:32:11)
> (Some bindings suppressed; use -fmax-relevant-binds=N or
> -fno-max-relevant-binds)
> Probable fix: use a type annotation to specify what `t0' should be.
> These potential instances exist:
> instance Ord Ordering -- Defined in `GHC.Classes'
> instance Ord Integer
> -- Defined in `integer-gmp-1.0.0.1:GHC.Integer.Type'
> instance Ord a => Ord (Maybe a) -- Defined in `GHC.Base'
> ...plus 22 others
> ...plus five instances involving out-of-scope types
> (use -fprint-potential-instances to see them all)
> * In the expression: apply_listd l d x
> In a case alternative: Leaf h l | h == k -> apply_listd l d x
> In the expression:
> case t of {
> Leaf h l | h == k -> apply_listd l d x
> Branch p b l r
> | (k `xor` p) .&. (b - 1) == 0
> -> look (if k .&. b == 0 then l else r)
> _ -> d x }
>
>
> --
> Best wishes,
> Ivan Kush
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
> ------------------------------
>
> End of Beginners Digest, Vol 103, Issue 25
> ******************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20170130/200f246b/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 30 Jan 2017 09:48:38 +0100
From: sasa bogicevic <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] applicative instance
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Wow thanks for the indepth explanation. I am glad that this got you reading
some stuff but the fact is I was just doing an exercise in writing Applicative
instances for some types and it was not stated that we should use separate
'helper' functions to achieve this. So I banged my head trying to write the
correct implementation but I could only come up with the zipList solution.
Thanks again!
Sasa
> On Jan 30, 2017, at 06:57, Graham Gill <[email protected]> wrote:
>
>
> On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
>> Is there a way to do it without defining a separate function like plusPlus ?
>
> My guess is there isn't. I'm unsure what you mean by your question though.
>
> Your List is a reimplementation of Haskell []. So, List with the "Cartesian
> product" Applicative instance will, like Haskell [], extend to a Monad
> instance. In the Monad instance for [], join = concat, and the work of concat
> is done using ++.
>
> For List, we can implement join using concatList:
>
> concatList :: List (List a) -> List a
> concatList Nil = Nil
> concatList (Cons xs xss) = xs `plusPlus` (concatList xss)
>
> and then we can add a Monad instance for List:
>
> instance Monad List where
> return = pure
> xs >>= f = concatList (pure f <*> xs)
>
> or equivalently, bind is given by
> xs >>= f = concatList (fmap f xs)
>
> To ask whether you can define the Cartesian product Applicative instance for
> List without plusPlus, is, I think, like asking whether there is a Cartesian
> product Applicative instance for List (or []) which doesn't extend to a Monad
> instance. Because if it does extend to a Monad (that obeys the Monad laws),
> then there will exist an implementation of join :: List (List a) -> List a,
> and join will need to collapse a List of Lists into a List. A function like
> plusPlus is used to accomplish the collapse.
>
> That's "proof by hand waving."
>
> The Ziplist Applicative instance for List on the other hand can't be extended
> to a Monad instance without additional restrictions on the lengths of the
> lists. Your question led me to some interesting reading with a google search
> on "list monad vs ziplist". Thanks.
>
>
> On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
>> Yep that worked, thanks.
>> Is there a way to do it without defining a separate function like plusPlus ?
>>
>>
>>
>>
>>
>>
>>> On Jan 28, 2017, at 10:43, Francesco Ariis <[email protected]>
>>> wrote:
>>>
>>> On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
>>>
>>>> Ok so how would the implementation look to get the correct result ?
>>>> I can't seem to write something that will compile except ZipList version.
>>>>
>>> One way is by implementing your own (++):
>>>
>>> data List a = Nil | Cons a (List a) deriving (Eq, Show)
>>>
>>> plusPlus :: List a -> List a -> List a
>>> plusPlus Nil bs = bs
>>> plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)
>>>
>>> instance Functor List where
>>> fmap f Nil = Nil
>>> fmap f (Cons a b) = Cons (f a) (fmap f b)
>>>
>>> instance Applicative List where
>>> pure x = Cons x Nil
>>> Nil <*> _ = Nil
>>> _ <*> Nil = Nil
>>> (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>>
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> _______________________________________________
>> Beginners mailing list
>>
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 103, Issue 26
******************************************
