headers
Twan van Laarhoven | 8 Mar 2007 21:00
Picon
Gravatar

Deriving Functor

Hello,

I would like to propose to add a way to automatically derive instances 
of Functor. From looking at existing code, it seems that almost all 
Functor instances I see are derivable using the algorithm presented 
here, resulting in less boilerplate code. This proposal is compatible 
with Haskell98 (and therefore also with Haskell').

Let's start with an example. The following declaration:

 > data Tree a = Leaf | Node (Tree a) a (Tree a)
 >      deriving Functor

would generate the following Functor instance:

 > instance Functor Tree where
 >      fmap f (Leaf      ) = Leaf
 >      fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)

To be able to derive Functor in a general way, more classes are needed 
to support functors over other parameters:
 > class Functor2 f where  fmap2  :: (a -> b) -> f a x   -> f b x
 > class Functor3 f where  fmap3  :: (a -> b) -> f a x y -> f b x y
 > -- etc.
Provided instances would be:
 > instance Functor  ((,) a)  -- currently in Control.Monad.Instances
 > instance Functor2  (,)
 > instance Functor  ((,,) a b)
 > instance Functor2 ((,,) a)
 > instance Functor3  (,,)
(Continue reading)

Permalink | Reply | 1 comment |
headers
Ross Paterson | 11 Mar 2007 13:10
Picon
Favicon

Re: Deriving Functor

On Thu, Mar 08, 2007 at 09:00:51PM +0100, Twan van Laarhoven wrote:
> I would like to propose to add a way to automatically derive instances 
> of Functor. From looking at existing code, it seems that almost all 
> Functor instances I see are derivable using the algorithm presented 
> here, resulting in less boilerplate code. This proposal is compatible 
> with Haskell98 (and therefore also with Haskell').

I don't know if you've seen Ralf Hinze's "Polytypic values possess
polykinded types", but the map example there is relevant.  (Also to the
semantics of newtype deriving that you posted a while ago.)

	http://www.informatik.uni-bonn.de/~ralf/publications/SCP.ps.gz

Even if you handle contrapositive arguments (like the first argument
of ->), there will still be things like

	newtype Endo a = Endo (a -> a)
Permalink | Reply | 0 comments |
headers
Ian Lynagh | 13 Mar 2007 21:41
Picon
Gravatar

Re: [GHC] #1215: GHC fails to respect the maximal munch rule while lexing "qualified reservedids"


Context if you haven't been following:
http://hackage.haskell.org/trac/ghc/ticket/1215

On Tue, Mar 13, 2007 at 03:12:33PM -0000, GHC wrote:
> 
>  Interesting.  It turns out I misinterpreted the Haskell lexical syntax:
>  GHC lexes `M.default` as `M` `.` `default`, because `M.default` is not a
>  valid qvarid but I neglected to take into account the maximal munch rule.
> 
>  We have an open ticket for Haskell' about this:
>  http://hackage.haskell.org/cgi-bin/haskell-prime/trac.cgi/wiki/QualifiedIdentifiers
>  which was until just now
>  inaccurate (I've now fixed it).  I propose to fix GHC in 6.8 to match the
>  Haskell' proposal.

If I understand correctly then the proposal would make e.g.

    foo = Bar.where

a syntactically valid program, but one which would be guaranteed to fail
to compile with a not-in-scope error?

Wouldn't it be cleaner for it to be a lexical error? Unfortunately I'm
not sure how to say this in the grammar; the best I can come up with is:

    program      ->      {lexeme | whitespace | error }
    error        ->      [ modid . ] reservedid

Thanks
(Continue reading)

Permalink | Reply | 1 comment |
headers
Simon Marlow | 14 Mar 2007 14:19
Picon

Re: [GHC] #1215: GHC fails to respect the maximal munch rule while lexing "qualified reservedids"

Ian Lynagh wrote:
> Context if you haven't been following:
> http://hackage.haskell.org/trac/ghc/ticket/1215
> 
> On Tue, Mar 13, 2007 at 03:12:33PM -0000, GHC wrote:
>>  Interesting.  It turns out I misinterpreted the Haskell lexical syntax:
>>  GHC lexes `M.default` as `M` `.` `default`, because `M.default` is not a
>>  valid qvarid but I neglected to take into account the maximal munch rule.
>>
>>  We have an open ticket for Haskell' about this:
>>  http://hackage.haskell.org/cgi-bin/haskell-prime/trac.cgi/wiki/QualifiedIdentifiers
>>  which was until just now
>>  inaccurate (I've now fixed it).  I propose to fix GHC in 6.8 to match the
>>  Haskell' proposal.
> 
> If I understand correctly then the proposal would make e.g.
> 
>     foo = Bar.where
> 
> a syntactically valid program, but one which would be guaranteed to fail
> to compile with a not-in-scope error?
> 
> Wouldn't it be cleaner for it to be a lexical error? Unfortunately I'm
> not sure how to say this in the grammar; the best I can come up with is:
> 
>     program      ->      {lexeme | whitespace | error }
>     error        ->      [ modid . ] reservedid

Or make lexeme overlap with error, and do this:
(Continue reading)

Permalink | Reply | 0 comments |
headers
Ian Lynagh | 16 Mar 2007 16:50
Picon
Gravatar

strict bits of datatypes


Hi all,

A while ago there was a discussion on haskell-cafe about the semantics
of strict bits in datatypes that never reached a conclusion; I've
checked with Malcolm and there is still disagreement about the right
answer. The original thread is around here:
http://www.haskell.org/pipermail/haskell-cafe/2006-October/018804.html
but I will try to give all the relevant information in this message.

The question is, given:

    data Fin a = FinCons a !(Fin a) | FinNil

    w = let q = FinCons 3 q
        in case q of
               FinCons i _ -> i

is w 3 or _|_?

---------- The _|_ argument ----------

(Supporters include me, ghc and hugs)

    q = FinCons 3 q
=== (by Haskell 98 report 4.2.1/Strictness Flags/Translation
    q = (FinCons $ 3) $! q
=== (by definition of $, $!)
    q = q `seq` FinCons 3 q
=== (solution is least fixed point of the equation)
(Continue reading)

Permalink | Reply | 22 comments |
headers
apfelmus | 16 Mar 2007 17:40
Picon
Favicon
Gravatar

Re: strict bits of datatypes

Ian Lynagh wrote:
> Here I will just quote what Malcolm said in his original message:
> 
>     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.

Well, in a sense, it's exactly the defining property of strict
constructors that they are not automatically different from _|_.

The translation

>     q = FinCons 3 q
> === (by Haskell 98 report 4.2.1/Strictness Flags/Translation
>     q = (FinCons $ 3) $! q

is rather subtle: the first FinCons is a strict constructor whereas the
second is "the real constructor". In other words, the translation loops
as we could (should?) apply

    FinCons
 => \x y -> FinCons x $! y
 => \x y -> (\x' y' -> FinCons x' $! y') x $! y
 => ...
(Continue reading)

Permalink | Reply | 12 comments |
headers
Jón Fairbairn | 16 Mar 2007 18:00
X-Face
Picon
Picon
Favicon

Re: strict bits of datatypes

apfelmus@... writes:

> Besides, having
> 
>   let q = FinCons 3 q in q
> 
> not being _|_ crucially depends on memoization. 

Does it? Mentally I translate that as 

   let q = Y (\q -> FinCons 3 q) in q

=>
   Y (\q-> FinCons 3 q)
=>
   (\q -> FinCons 3 q) (Y (\q-> FinCons 3 q))
=>
   FinCons 3 (Y (\q -> FinCons 3 q))

which, assuming a plausible lambda expression for FinCons,
is a soluble term.

> Even with the characterization by WHNF,
> 
>   let q x = FinCons 3 (q x) in q ()
> 
> is _|_.

Again
(Continue reading)

Permalink | Reply | 8 comments |
headers
Ross Paterson | 16 Mar 2007 19:10
Picon
Favicon

Re: strict bits of datatypes

On Fri, Mar 16, 2007 at 05:40:17PM +0100, apfelmus@... wrote:
> The translation
> 
> >     q = FinCons 3 q
> > === (by Haskell 98 report 4.2.1/Strictness Flags/Translation
> >     q = (FinCons $ 3) $! q
> 
> is rather subtle: the first FinCons is a strict constructor whereas the
> second is "the real constructor". In other words, the translation loops
> as we could (should?) apply
> 
>     FinCons
>  => \x y -> FinCons x $! y
>  => \x y -> (\x' y' -> FinCons x' $! y') x $! y
>  => ...
> 
> ad infinitum.

Yes, perhaps that ought to be fixed.  But even so, this clearly implies that

	FinCons 3 _|_ = _|_

and thus that q is _|_ and nhc98/yhc have a bug.
Permalink | Reply | 2 comments |
headers
Iavor Diatchki | 16 Mar 2007 19:16
Picon
Gravatar

Re: strict bits of datatypes

Hello,
I also think that the first version is the correct one (i.e., the
result is _|_).
-Iavor

On 3/16/07, Ross Paterson <ross@...> wrote:
> On Fri, Mar 16, 2007 at 05:40:17PM +0100, apfelmus@... wrote:
> > The translation
> >
> > >     q = FinCons 3 q
> > > === (by Haskell 98 report 4.2.1/Strictness Flags/Translation
> > >     q = (FinCons $ 3) $! q
> >
> > is rather subtle: the first FinCons is a strict constructor whereas the
> > second is "the real constructor". In other words, the translation loops
> > as we could (should?) apply
> >
> >     FinCons
> >  => \x y -> FinCons x $! y
> >  => \x y -> (\x' y' -> FinCons x' $! y') x $! y
> >  => ...
> >
> > ad infinitum.
>
> Yes, perhaps that ought to be fixed.  But even so, this clearly implies that
>
>         FinCons 3 _|_ = _|_
>
> and thus that q is _|_ and nhc98/yhc have a bug.
>
(Continue reading)

Permalink | Reply | 0 comments |
headers
John Meacham | 16 Mar 2007 19:28
Favicon

Re: strict bits of datatypes

On Fri, Mar 16, 2007 at 05:00:15PM +0000, Jón Fairbairn wrote:
> Does it? Mentally I translate that as 
> 
>    let q = Y (\q -> FinCons 3 q) in q
> 

but it would actually translate to

>    let q = Y (\q -> q `seq` FinCons 3 q) in q

for strict fields, whenever a constructor appears, it is translated to
one which seq's its strict fields before creating the constructor.

so,

FinCons 3 q 
desugars to

q `seq` FinCons 3 q wherever it appears,

strict fields have no effect on deconstructing data types.

        John

--

-- 
John Meacham - ⑆repetae.net⑆john⑈
Permalink | Reply | 5 comments |

Gmane