Pointed, but not Applicative

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Pointed, but not Applicative

Soenke Hahn
Hi!

I was reading through the Typeclassopedia ([1]) and I was wondering which
type could be an instance of Pointed, but not of Applicative. But I can't
think of one. Any ideas?

Sönke

[1] http://www.haskell.org/haskellwiki/Typeclassopedia


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Tony Morris-4
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 28/08/11 01:41, Sönke Hahn wrote:

> Hi!
>
> I was reading through the Typeclassopedia ([1]) and I was wondering which
> type could be an instance of Pointed, but not of Applicative. But I can't
> think of one. Any ideas?
>
> Sönke
>
> [1] http://www.haskell.org/haskellwiki/Typeclassopedia
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Pointed f => Pointed (StateT s f)

but not

Applicative f => Applicative (StateT s f)

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOWhtaAAoJEPxHMY3rBz0Pa3oIAMrqoyv4DW39VjIXwzV3/4Ir
W5s0+fdoPj7h1j6eyCB81VcDHNtGQmWhZ3+g2AhHo1jLAzmH8G5ACdD1c1FeF2dn
a0iO7uvH5sM0xovpsqUwZC8BkomdeAnRuYF5Ohzar5M/Ip2BD0k7QpIWJt3RdLZm
uCpwDnsQ2foHJCJYlGmmGkpzDAnkwePOfER93KrKXmzHqQxhS0oACQy6LKfXODTM
+d2VVzzb4tWuzijXE4NflpdtW/4jSs3gVFmkZ7BmXSg8XxZO3naO/y4gtrU4YVjw
7TKo4IOIygQVMsFbdV2WZHprMHU/VaM6MTByiNECyB0q/yhJhsXtGsd9eeR2jng=
=X4nM
-----END PGP SIGNATURE-----

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Felipe Lessa
On Sun, Aug 28, 2011 at 7:41 AM, Tony Morris <[hidden email]> wrote:
> Pointed f => Pointed (StateT s f)
>
> but not
>
> Applicative f => Applicative (StateT s f)

But we do have

    (Functor m, Monad m) => Applicative (StateT s m)

so I'm not sure if this is a valid example.

Cheers,

--
Felipe.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Maciej Piechotka
On Sun, 2011-08-28 at 11:48 -0300, Felipe Almeida Lessa wrote:

> On Sun, Aug 28, 2011 at 7:41 AM, Tony Morris <[hidden email]> wrote:
> > Pointed f => Pointed (StateT s f)
> >
> > but not
> >
> > Applicative f => Applicative (StateT s f)
>
> But we do have
>
>     (Functor m, Monad m) => Applicative (StateT s m)
>
> so I'm not sure if this is a valid example.
>
> Cheers,
>
newtype StateT s m a = StateT (s -> m (a, s))

instance Functor m => Functor (StateT s m) where
  f `fmap` StateT g = StateT $ fmap (first f) . g

instance Pointed m => Pointed (StateT s m) where
  point x = StateT $ point . (,) x

Regards

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Sebastian Fischer-2
In reply to this post by Soenke Hahn
On Sun, Aug 28, 2011 at 12:41 AM, Sönke Hahn <[hidden email]> wrote:
> I was wondering which
> type could be an instance of Pointed, but not of Applicative. But I can't
> think of one. Any ideas?

Functional lists:

    type FList a = [a] -> [a]

they have a Monoid instance for empty and append, a "point" function
for singletons but Applicative or Monad cannot be defined without
converting back and forth to ordinary lists.

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Maciej Piechotka
On Mon, 2011-08-29 at 12:00 +0900, Sebastian Fischer wrote:

> On Sun, Aug 28, 2011 at 12:41 AM, Sönke Hahn <[hidden email]> wrote:
> > I was wondering which
> > type could be an instance of Pointed, but not of Applicative. But I can't
> > think of one. Any ideas?
>
> Functional lists:
>
>     type FList a = [a] -> [a]
>
> they have a Monoid instance for empty and append, a "point" function
> for singletons but Applicative or Monad cannot be defined without
> converting back and forth to ordinary lists.
>
> Sebastian
newtype FList a = FList ([a] -> [a])

instance Functor FList where
    f `fmap` FList g = ...?

The only possible implementation I can think of:

f `fmap` FList g = _|_
f `fmap` FList g = map id
f `fmap` FList g = map _|_
(+ variation of _|_*)

Neither of them holding fmap id = id.

Regards

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Sebastian Fischer-2
On Mon, Aug 29, 2011 at 12:24 PM, Maciej Marcin Piechotka
<[hidden email]> wrote:

> instance Functor FList where
>    f `fmap` FList g = ...?

Yes, Functor is also one of the classes that can only be implemented
by converting to ordinary lists (I think).

So FList could only be made an instance of Pointed without (certain)
superclass constraints.

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Ryan Ingram
In reply to this post by Maciej Piechotka


On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka <[hidden email]> wrote:
f `fmap` FList g = _|_
f `fmap` FList g = map id
f `fmap` FList g = map _|_
(+ variation of _|_*)

f `fmap` FList g = \bs -> map f (g []) ++ bs



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Maciej Piechotka
On Mon, 2011-08-29 at 20:24 -0700, Ryan Ingram wrote:

>
>
> On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka
> <[hidden email]> wrote:
>         f `fmap` FList g = _|_
>         f `fmap` FList g = map id
>         f `fmap` FList g = map _|_
>         (+ variation of _|_*)
>
> f `fmap` FList g = \bs -> map f (g []) ++ bs
>

You mean

f `fmap` FList g = FList $ \bs -> map f (g []) ++ bs

>
>

Seems to confirm to second law as well.

Regards


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Soenke Hahn
In reply to this post by Tony Morris-4
Tony Morris wrote:

> Pointed f => Pointed (StateT s f)
>
> but not
>
> Applicative f => Applicative (StateT s f)

I see. So StateT cannot be what you could call an applicative transformer.
(Unlike for example ReaderT.)

Thanks.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Conal Elliott
In reply to this post by Ryan Ingram
I suspect this definition is what Sebastian meant by "converting back and forth to ordinary lists".

2011/8/29 Ryan Ingram <[hidden email]>


On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka <[hidden email]> wrote:
f `fmap` FList g = _|_
f `fmap` FList g = map id
f `fmap` FList g = map _|_
(+ variation of _|_*)

f `fmap` FList g = \bs -> map f (g []) ++ bs



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Ryan Ingram
On Tue, Aug 30, 2011 at 9:42 AM, Conal Elliott <[hidden email]> wrote:
> I suspect this definition is what Sebastian meant by "converting back and forth to ordinary lists".

Yep, I know; and technically it violates 'fmap id' == 'id'

for example,
fmap id (FList $ \xs -> xs ++ xs) = FList $ \xs -> xs

If you add this FList law, though, you're OK:

runFList fl as = runFList fl [] ++ as

But, yes, this definition of fmap converts back to an ordinary list representation.

  -- ryan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Sebastian Fischer-2
On Wed, Aug 31, 2011 at 6:13 AM, Ryan Ingram <[hidden email]> wrote:
> technically it violates 'fmap id' == 'id' [...]
>
> If you add this FList law, though, you're OK:
>
> runFList fl as = runFList fl [] ++ as

I think the idea of functional lists is that the monoids of 'lists'
and 'functions on lists' are isomorphic with isomorphisms toFList and
toList:

    toFList [] = id
    toFList (xs++ys) = toFList xs . toFList ys

    toList id = []
    toList (f . g) = toList f ++ toList g

These can be defined as:

    toFList = (++)
    toList = ($[])

Eliding newtypes, runFList is just the identity function so we need to check

    f l = toList f ++ l

to verify your law. This is the same as

    f = toFList (toList f)

which (once we know that toList and toFList are isomorphisms) does
indeed hold because:

    toFList . toList = id
    toList . toFList = id

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Sebastian Fischer-2
>    toFList [] = id
>    toFList (xs++ys) = toFList xs . toFList ys
>
>    toList id = []
>    toList (f . g) = toList f ++ toList g

These laws do not *define* the isomorphisms because their behavior on
singletons is not fixed. Combining them with laws using a 'point'
function for functional lists

    point = (:)

the isomorphisms are characterized uniquely:

    toFList [x] = point x
    toList (point x) = [x]

This might be an argument in favor of a Pointed class without Functor
constraint as it shows that other pointed structures have reasonable
laws involving 'point' as well.

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

roconnor
In reply to this post by Soenke Hahn
On Sat, 27 Aug 2011, Sönke Hahn wrote:

> Hi!
>
> I was reading through the Typeclassopedia ([1]) and I was wondering which
> type could be an instance of Pointed, but not of Applicative. But I can't
> think of one. Any ideas?

(Identity :+: Store s) is a comonad that is also instance of Pointed, but
I do not believe it is an instance Applicative.

newtype SemiStore s a = (Identity :+: Store s) a

instance Pointed (SemiStore s) where
   pure a = Inl (Identity a)

Coalgebras of the (Identity :+: Store s) comonad form the type of partial
lenses so this isn't just an academic functor.

--
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

roconnor
On Wed, 31 Aug 2011, [hidden email] wrote:

> On Sat, 27 Aug 2011, Sönke Hahn wrote:
>
>> Hi!
>>
>> I was reading through the Typeclassopedia ([1]) and I was wondering which
>> type could be an instance of Pointed, but not of Applicative. But I can't
>> think of one. Any ideas?
>
> (Identity :+: Store s) is a comonad that is also instance of Pointed, but I
> do not believe it is an instance Applicative.
>
> newtype SemiStore s a = (Identity :+: Store s) a
>
> instance Pointed (SemiStore s) where
>  pure a = Inl (Identity a)
>
> Coalgebras of the (Identity :+: Store s) comonad form the type of partial
> lenses so this isn't just an academic functor.
Sorry I left out the newtype wrappers:

newtype SemiStore s a = SemiStore ((Identity :+: Store s) a)

instance Pointed (SemiStore s) where
   pure = SemiStore . Inl . Identity

--
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Pointed, but not Applicative

Ryan Ingram
In reply to this post by Sebastian Fischer-2
On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer <[hidden email]> wrote:
I think the idea of functional lists is that the monoids of 'lists'
and 'functions on lists' are isomorphic with isomorphisms toFList and
toList:

   toFList [] = id
   toFList (xs++ys) = toFList xs . toFList ys

   toList id = []
   toList (f . g) = toList f ++ toList g

Oh absolutely, but my point (if you will pardon the pun), was that just given the type

newtype FList a = FL ([a] -> [a])
runFList (FL f) = f

and the law

runFList fl as = runFList fl [] ++ as

we can prove that

fmap f fl = FL $ \bs -> map f (runFList fl []) ++ bs

is a valid functor instance:

fmap id
(eta expand) = \fl -> fmap id fl
(apply fmap) = \fl -> FL $ \bs -> map id (runFList fl []) ++ bs
(map law) = \fl -> FL $ \bs -> id (runFList fl []) ++ bs
(apply id) = \fl -> FL $ \bs -> runFList fl [] ++ bs
(FList law) = \fl -> FL $ \bs -> runFList fl bs
(eta reduce) = \fl -> FL $ runFList fl
(constructor of destructor) = \fl -> fl
(unapply id) = \fl -> id fl
(eta reduce) = id

We don't need to know that FList is supposed to represent an isomorphism to/from lists, although you can derive one, as you've shown.  I just wanted to show that it's a valid functor, but only if you assume an extra law on the type.  The functor instance depends critically on converting back to a list which requires that law.

There's no functor instance for this type that doesn't convert back to a list, which is unfortunate, because you lose the performance benefits of constant-time append!

  -- ryan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe