From conal at conal.net Sat Dec 2 17:50:44 2017
From: conal at conal.net (Conal Elliott)
Date: Sat, 2 Dec 2017 09:50:44 -0800
Subject: Rewrite rules involving LHS lambda?
Message-ID:
Is there a written explanation and/or examples of rewrite rules involving a
LHS lambda? Since rule matching is first-order, I'm wondering how terms
with lambda are matched on the LHS and substituted into on the RHS. For
instance, I want to restructure a lambda term as follows:
> foo (\ x -> fmap u v) = bar (\ x -> u) (\ x -> v)
My intent is that the terms `u` and `v` may contain `x` and that whatever
variable name is actually used in a term being rewritten is preserved so as
to re-capture its occurrences on the RHS.
When I write this sort of rule, I get warnings about `x` being defined but
not used.
Thanks, -- Conal
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From ekmett at gmail.com Sat Dec 2 20:20:43 2017
From: ekmett at gmail.com (Edward Kmett)
Date: Sun, 3 Dec 2017 07:20:43 +1100
Subject: Rewrite rules involving LHS lambda?
In-Reply-To:
References:
Message-ID:
I don't knw of a formal writeup anywhere.
But does that actually mean what you are trying to write?
With the effective placement of "forall" quantifiers on the outside for u
and v I'd assume that x didn't occur in either u or v. Effectively you have
some scope like forall u v. exists x. ...
Under that view, the warnings are accurate, and the rewrite is pretty
purely syntactic.
I don't see how we could write using our current vocabulary that which you
want.
On Sun, Dec 3, 2017 at 4:50 AM, Conal Elliott wrote:
> Is there a written explanation and/or examples of rewrite rules involving
> a LHS lambda? Since rule matching is first-order, I'm wondering how terms
> with lambda are matched on the LHS and substituted into on the RHS. For
> instance, I want to restructure a lambda term as follows:
>
> > foo (\ x -> fmap u v) = bar (\ x -> u) (\ x -> v)
>
> My intent is that the terms `u` and `v` may contain `x` and that whatever
> variable name is actually used in a term being rewritten is preserved so as
> to re-capture its occurrences on the RHS.
>
> When I write this sort of rule, I get warnings about `x` being defined but
> not used.
>
> Thanks, -- Conal
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From conal at conal.net Sat Dec 2 20:59:30 2017
From: conal at conal.net (Conal Elliott)
Date: Sat, 2 Dec 2017 12:59:30 -0800
Subject: Rewrite rules involving LHS lambda?
In-Reply-To:
References:
Message-ID:
Thanks for the reply, Ed.
> I'd assume that `x` didn't occur in either `u` or `v`
This is exactly the issue I'm wondering about. Since rewrite rules admit
lambdas and only first-order matching, I'm wondering whether they're
interpreted as you did (and I'd tend to), namely that `x` doesn't occur
freely in `u`or `v`, in which case lambdas don't seem useful in rules (and
yet were implemented for some reason) or they're interpreted as allowing
`x` in `u` and `v`, and substitution captures. I'm still puzzled.
With a wee bit of higher-order matching, one might make `u` and `v`
functions and instead write:
> foo (\ x -> fmap (u x) (v x)) = bar u v
In that case I'd expect `u` and `v` to be synthesized rather than literally
matched. For instance, `foo (\ (a,b) -> fmap (+ a) [b,b,b])` would match
with `u = \ (a,b) -> (+ a)` and `v = \ (a,b) -> [b,b,b]`.
-- Conal
On Sat, Dec 2, 2017 at 12:20 PM, Edward Kmett wrote:
> I don't knw of a formal writeup anywhere.
>
> But does that actually mean what you are trying to write?
>
> With the effective placement of "forall" quantifiers on the outside for u
> and v I'd assume that x didn't occur in either u or v. Effectively you have
> some scope like forall u v. exists x. ...
>
> Under that view, the warnings are accurate, and the rewrite is pretty
> purely syntactic.
>
> I don't see how we could write using our current vocabulary that which you
> want.
>
> On Sun, Dec 3, 2017 at 4:50 AM, Conal Elliott wrote:
>
>> Is there a written explanation and/or examples of rewrite rules involving
>> a LHS lambda? Since rule matching is first-order, I'm wondering how terms
>> with lambda are matched on the LHS and substituted into on the RHS. For
>> instance, I want to restructure a lambda term as follows:
>>
>> > foo (\ x -> fmap u v) = bar (\ x -> u) (\ x -> v)
>>
>> My intent is that the terms `u` and `v` may contain `x` and that whatever
>> variable name is actually used in a term being rewritten is preserved so as
>> to re-capture its occurrences on the RHS.
>>
>> When I write this sort of rule, I get warnings about `x` being defined
>> but not used.
>>
>> Thanks, -- Conal
>>
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From mail at joachim-breitner.de Sat Dec 2 21:56:27 2017
From: mail at joachim-breitner.de (Joachim Breitner)
Date: Sat, 02 Dec 2017 16:56:27 -0500
Subject: Rewrite rules involving LHS lambda?
In-Reply-To:
References:
Message-ID: <1512251787.21922.9.camel@joachim-breitner.de>
Hi,
Am Samstag, den 02.12.2017, 12:59 -0800 schrieb Conal Elliott:
> Thanks for the reply, Ed.
>
> > I'd assume that `x` didn't occur in either `u` or `v`
>
> This is exactly the issue I'm wondering about. Since rewrite rules
> admit lambdas and only first-order matching, I'm wondering whether
> they're interpreted as you did (and I'd tend to), namely that `x`
> doesn't occur freely in `u`or `v`, in which case lambdas don't seem
> useful in rules (and yet were implemented for some reason)
even with these restrictions, they are still useful for rules like
map (\x -> x) = id
> With a wee bit of higher-order matching, one might make `u` and `v`
> functions and instead write:
>
> > foo (\ x -> fmap (u x) (v x)) = bar u v
>
> In that case I'd expect `u` and `v` to be synthesized rather than
> literally matched. For instance, `foo (\ (a,b) -> fmap (+ a)
> [b,b,b])` would match with `u = \ (a,b) -> (+ a)` and `v = \ (a,b) ->
> [b,b,b]`.
That would be nice and interesting, but we don’t do that now,
unfortunately.
And of course higher-order pattern matching is quite a can of worms. I
implemented it in http://incredible.pm/ but that was a much simpler
setting than a complex typed language like Core.
Implementing some form of higher-order pattern matching might actually
be doable, but would it be reliable? When does it become undecidable?
Joachim
--
Joachim Breitner
mail at joachim-breitner.de
http://www.joachim-breitner.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL:
From 78emil at gmail.com Sun Dec 3 17:53:49 2017
From: 78emil at gmail.com (Emil Axelsson)
Date: Sun, 3 Dec 2017 17:53:49 +0000
Subject: Rewrite rules involving LHS lambda?
In-Reply-To: <1512251787.21922.9.camel@joachim-breitner.de>
References:
<1512251787.21922.9.camel@joachim-breitner.de>
Message-ID: <369da962-71c5-02c5-a9ca-b8ad570e4c7a@gmail.com>
Den 2017-12-02 kl. 21:56, skrev Joachim Breitner:
>> With a wee bit of higher-order matching, one might make `u` and `v`
>> functions and instead write:
>>
>>> foo (\ x -> fmap (u x) (v x)) = bar u v
>>
>> In that case I'd expect `u` and `v` to be synthesized rather than
>> literally matched. For instance, `foo (\ (a,b) -> fmap (+ a)
>> [b,b,b])` would match with `u = \ (a,b) -> (+ a)` and `v = \ (a,b) ->
>> [b,b,b]`.
>
>
> That would be nice and interesting, but we don’t do that now,
> unfortunately.
>
> And of course higher-order pattern matching is quite a can of worms. I
> implemented it in http://incredible.pm/ but that was a much simpler
> setting than a complex typed language like Core.
>
> Implementing some form of higher-order pattern matching might actually
> be doable, but would it be reliable? When does it become undecidable?
Miller's pattern unification is quite useful for rewriting, and the
above example falls within that (all meta-variables are applied only to
object variables). Rewriting based on pattern unification is decidable
and efficient; see this paper:
http://www.cse.chalmers.se/~emax/documents/axelsson2015lightweight.pdf
However, that paper assumes a normalized representation, so I'm not sure
how well it would work in a compiler like GHC.
/ Emil
> Joachim
>
>
>
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
From post at volker-wysk.de Sun Dec 3 18:24:17 2017
From: post at volker-wysk.de (Volker Wysk)
Date: Sun, 03 Dec 2017 19:24:17 +0100
Subject: How to uninstall all cabal packages?
Message-ID: <14694646.4BNroYIbr0@desktop>
Hi!
I want to remove eveything which cabal has installed, and begin again with a clean installation. How is this accomplished? I've deleted ~/.cabal, but it still says that hsshellscript is already installed:
desktop ~ $ cabal install hsshellscript
Resolving dependencies...
All the requested packages are already installed:
hsshellscript-3.4.3
Use --reinstall if you want to reinstall anyway.
Bye
V.W.
From michael at snoyman.com Sun Dec 3 18:32:20 2017
From: michael at snoyman.com (Michael Snoyman)
Date: Sun, 3 Dec 2017 20:32:20 +0200
Subject: How to uninstall all cabal packages?
In-Reply-To: <14694646.4BNroYIbr0@desktop>
References: <14694646.4BNroYIbr0@desktop>
Message-ID:
You'll need to delete your ~/.ghc directory as well.
On Sun, Dec 3, 2017 at 8:24 PM, Volker Wysk wrote:
> Hi!
>
> I want to remove eveything which cabal has installed, and begin again with
> a clean installation. How is this accomplished? I've deleted ~/.cabal, but
> it still says that hsshellscript is already installed:
>
> desktop ~ $ cabal install hsshellscript
> Resolving dependencies...
> All the requested packages are already installed:
> hsshellscript-3.4.3
> Use --reinstall if you want to reinstall anyway.
>
> Bye
> V.W.
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From thomas.dubuisson at gmail.com Sun Dec 3 18:33:33 2017
From: thomas.dubuisson at gmail.com (Thomas DuBuisson)
Date: Sun, 3 Dec 2017 10:33:33 -0800
Subject: How to uninstall all cabal packages?
In-Reply-To: <14694646.4BNroYIbr0@desktop>
References: <14694646.4BNroYIbr0@desktop>
Message-ID:
Packages registered with ghc are placed in the .ghc directory. You can
delete the directory entirely or selectively unregister using ghc-pkg.
On Dec 3, 2017 10:31 AM, "Volker Wysk" wrote:
> Hi!
>
> I want to remove eveything which cabal has installed, and begin again with
> a clean installation. How is this accomplished? I've deleted ~/.cabal, but
> it still says that hsshellscript is already installed:
>
> desktop ~ $ cabal install hsshellscript
> Resolving dependencies...
> All the requested packages are already installed:
> hsshellscript-3.4.3
> Use --reinstall if you want to reinstall anyway.
>
> Bye
> V.W.
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From post at volker-wysk.de Sun Dec 3 18:39:27 2017
From: post at volker-wysk.de (Volker Wysk)
Date: Sun, 03 Dec 2017 19:39:27 +0100
Subject: How to uninstall all cabal packages?
In-Reply-To:
References: <14694646.4BNroYIbr0@desktop>
Message-ID: <38789474.h3mjvALQGQ@desktop>
Yes, that's it. Thanks for the fast answer!
Am Sonntag, 3. Dezember 2017, 20:32:20 CET schrieb Michael Snoyman:
> You'll need to delete your ~/.ghc directory as well.
>
> On Sun, Dec 3, 2017 at 8:24 PM, Volker Wysk wrote:
>
> > Hi!
> >
> > I want to remove eveything which cabal has installed, and begin again with
> > a clean installation. How is this accomplished? I've deleted ~/.cabal, but
> > it still says that hsshellscript is already installed:
> >
> > desktop ~ $ cabal install hsshellscript
> > Resolving dependencies...
> > All the requested packages are already installed:
> > hsshellscript-3.4.3
> > Use --reinstall if you want to reinstall anyway.
> >
> > Bye
> > V.W.
> >
> > _______________________________________________
> > Glasgow-haskell-users mailing list
> > Glasgow-haskell-users at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
> >
>
From post at volker-wysk.de Sun Dec 3 18:40:16 2017
From: post at volker-wysk.de (Volker Wysk)
Date: Sun, 03 Dec 2017 19:40:16 +0100
Subject: How to uninstall all cabal packages?
In-Reply-To:
References: <14694646.4BNroYIbr0@desktop>
Message-ID: <1860684.8bos1Tg8Wy@desktop>
Again, thanks for the fast answer!
Volker
Am Sonntag, 3. Dezember 2017, 10:33:33 CET schrieb Thomas DuBuisson:
> Packages registered with ghc are placed in the .ghc directory. You can
> delete the directory entirely or selectively unregister using ghc-pkg.
>
> On Dec 3, 2017 10:31 AM, "Volker Wysk" wrote:
>
> > Hi!
> >
> > I want to remove eveything which cabal has installed, and begin again with
> > a clean installation. How is this accomplished? I've deleted ~/.cabal, but
> > it still says that hsshellscript is already installed:
> >
> > desktop ~ $ cabal install hsshellscript
> > Resolving dependencies...
> > All the requested packages are already installed:
> > hsshellscript-3.4.3
> > Use --reinstall if you want to reinstall anyway.
> >
> > Bye
> > V.W.
> >
> > _______________________________________________
> > Glasgow-haskell-users mailing list
> > Glasgow-haskell-users at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
> >
>
From carter.schonwald at gmail.com Tue Dec 12 03:22:12 2017
From: carter.schonwald at gmail.com (Carter Schonwald)
Date: Tue, 12 Dec 2017 03:22:12 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To: <5a1295b1.33d.372a.15211@clear.net.nz>
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
This was / perhaps still is one goal of injective type families too! I’m
not sure why the current status is, but it’s defjnitely related
On Mon, Nov 20, 2017 at 3:44 AM Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:
> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>
> (Moving to ghc-users, there's nothing particularly dev-y.)
>
> > Sometimes it woulld be useful to be able to reason
> backwards
> > about type families.
>
> Hi David, this is a well-known issue/bit of a sore.
> Discussed much in the debate between type families
> compared to FunDeps.
>
> > For example, we have
> >
> > type family a && b where
> > 'False && b = 'False
> > 'True && b = b
> > a && 'False = 'False
> > a && 'True = a
> > a && a = a
>
> > ... if we know something about the *result*,
> > GHC doesn't give us any way to learn anything about the
> arguments.
>
> You can achieve the improvement you want today.
>
> You'll probably find Oleg has a solution
> With FunDeps and superclass constraints, it'll go like this
>
> class (OnResult r a b, OnResult r b a) => And a b r | a b ->
> r
>
> instance And 'False b 'False
> -- etc, as you'd expect following the tf equations
> -- the instances are overlapping but confluent
>
> class OnResult r a b | r a -> b
> instance OnResult 'True a 'True
> instance OnResult 'False 'True 'False
>
> You could equally make `OnResult` a type family.
>
> If you can trace backwards to where `&&` is used,
> you might be able to add suitable constraints there.
>
> So there's a couple of futures:
> * typechecker plugins, using an SMT solver
> * injective type families
> the next phase is supposed to allow
>
> type family a && b = r | r a -> b, r b -> a where ...
>
> That will help with some type families
> (such as addition of Nats),
> plug1
>
> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#injective-type-families
>
> but I don't see it helping here.
> plug2 (this example)
>
> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#type-family-coincident-overlap
>
> Because (for example) if you unify the first two equations,
> (that is, looking for coincident overlap)
>
> 'False && 'False = 'False
> 'True && 'False = 'False
>
> That's inconsistent on dependency ` r b -> a`.
>
> And you can't fix it by re-ordering the closed equations.
>
> > For (&&), the obvious things you'd want are ...
> >
> > There's nothing inherently impossible about this sort of
> reasoning.
>
> No-ish but. It relies on knowing kind `Bool` is closed.
> And GHC doesn't pay attention to that.
> So you need to bring type family `Not`
> into the reasoning; hence a SMT solver.
>
> > ...
> > I wouldn't necessarily expect GHC
> > to be able to work something like this out on its own.
>
> That's a relief ;-)
>
> > But it seems like there should be some way to allow the
> user
> > to guide it to a proof.
>
> Yes, an SMT solver with a model for kind `Bool`.
> (And a lot of hard work to teach it, by someone.)
>
> AntC
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From anthony_clayden at clear.net.nz Thu Dec 14 00:29:56 2017
From: anthony_clayden at clear.net.nz (Anthony Clayden)
Date: Thu, 14 Dec 2017 00:29:56 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
On Tue, 12 Dec 2017 at 4:53 PM, Carter Schonwald
wrote:
> This was / perhaps still is one goal of injective type families too! I’m
> not sure why the current status is, but it’s defjnitely related
>
Thanks Carter, yes this sort of injectiviy (semi-injectivity? partial
injectivity?) is noted as future work in the 2015 paper. But I'm not seeing
a lot of hollerin' for it(?) Or am I looking in the wrong places?
The classic example is for Nats in length-indexed vectors: if we know the
length of appending two vectors, and one of the arguments, infer the length
of the other. (Oleg provided a solution using FunDeps more than a decade
ago.) But GHC has special handling for type-level Nats (or rather Ints),
hence no need to extend injectivity.
Come to that, the original work that delivered Injective Type Families
failed to find many use cases -- so the motivation was more
keep-up-with-the-Jones's to provide equivalence to FunDeps.
There were lots of newbie mistakes when Type Families first arrived, of
thinking they were injective, because a TF application looks like a type
constructor application `F Int` cp `T Int`. But perhaps that
misunderstanding didn't represent genuine use cases?
Is anybody out there using Injective Type Families currently? What for?
AntC
> On Mon, Nov 20, 2017 at 3:44 AM Anthony Clayden <
> anthony_clayden at clear.net.nz> wrote:
>
>> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>>
>> (Moving to ghc-users, there's nothing particularly dev-y.)
>>
>> > Sometimes it woulld be useful to be able to reason
>> backwards
>> > about type families.
>>
>> Hi David, this is a well-known issue/bit of a sore.
>> Discussed much in the debate between type families
>> compared to FunDeps.
>>
>> > For example, we have
>> >
>> > type family a && b where
>> > 'False && b = 'False
>> > 'True && b = b
>> > a && 'False = 'False
>> > a && 'True = a
>> > a && a = a
>>
>> > ... if we know something about the *result*,
>> > GHC doesn't give us any way to learn anything about the
>> arguments.
>>
>> You can achieve the improvement you want today.
>>
>> You'll probably find Oleg has a solution
>> With FunDeps and superclass constraints, it'll go like this
>>
>> class (OnResult r a b, OnResult r b a) => And a b r | a b ->
>> r
>>
>> instance And 'False b 'False
>> -- etc, as you'd expect following the tf equations
>> -- the instances are overlapping but confluent
>>
>> class OnResult r a b | r a -> b
>> instance OnResult 'True a 'True
>> instance OnResult 'False 'True 'False
>>
>> You could equally make `OnResult` a type family.
>>
>> If you can trace backwards to where `&&` is used,
>> you might be able to add suitable constraints there.
>>
>> So there's a couple of futures:
>> * typechecker plugins, using an SMT solver
>> * injective type families
>> the next phase is supposed to allow
>>
>> type family a && b = r | r a -> b, r b -> a where ...
>>
>> That will help with some type families
>> (such as addition of Nats),
>> plug1
>>
>> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#injective-type-families
>>
>> but I don't see it helping here.
>> plug2 (this example)
>>
>> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#type-family-coincident-overlap
>>
>> Because (for example) if you unify the first two equations,
>> (that is, looking for coincident overlap)
>>
>> 'False && 'False = 'False
>> 'True && 'False = 'False
>>
>> That's inconsistent on dependency ` r b -> a`.
>>
>> And you can't fix it by re-ordering the closed equations.
>>
>> > For (&&), the obvious things you'd want are ...
>> >
>> > There's nothing inherently impossible about this sort of
>> reasoning.
>>
>> No-ish but. It relies on knowing kind `Bool` is closed.
>> And GHC doesn't pay attention to that.
>> So you need to bring type family `Not`
>> into the reasoning; hence a SMT solver.
>>
>> > ...
>> > I wouldn't necessarily expect GHC
>> > to be able to work something like this out on its own.
>>
>> That's a relief ;-)
>>
>> > But it seems like there should be some way to allow the
>> user
>> > to guide it to a proof.
>>
>> Yes, an SMT solver with a model for kind `Bool`.
>> (And a lot of hard work to teach it, by someone.)
>>
>> AntC
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From clintonmead at gmail.com Thu Dec 14 00:54:22 2017
From: clintonmead at gmail.com (Clinton Mead)
Date: Thu, 14 Dec 2017 11:54:22 +1100
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
Injective Type Families are at the core of my "Freelude" (
https://hackage.haskell.org/package/freelude) package, which allows many
more types to be defined as Categories, Functors, Applicatives and Monads.
For example you can define a tuple of categories as a category and then:
(f1, f2) . (g1 . g2) = (f1 . g1, f2 . g2)
as one would expect.
Also one can define symmetric versions on tuples "fmap", for example:
fmap (*2) (3,4,5) = (6,8,10)
The library is currently basically a proof of concept but it wouldn't be
possible without Injective Type Families.
What would also be helpful is if injectivity of type C as mentioned on the
page (https://ghc.haskell.org/trac/ghc/wiki/InjectiveTypeFamilies) but
unfortunately this is currently not implemented so I've worked around this
where possible (this is largely the reason why the library splits
"Functors" and "ExoFunctors").
Cheers,
Clinton
On Thu, Dec 14, 2017 at 11:29 AM, Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:
>
> On Tue, 12 Dec 2017 at 4:53 PM, Carter Schonwald
> wrote:
>
>> This was / perhaps still is one goal of injective type families too! I’m
>> not sure why the current status is, but it’s defjnitely related
>>
>
> Thanks Carter, yes this sort of injectiviy (semi-injectivity? partial
> injectivity?) is noted as future work in the 2015 paper. But I'm not seeing
> a lot of hollerin' for it(?) Or am I looking in the wrong places?
>
> The classic example is for Nats in length-indexed vectors: if we know the
> length of appending two vectors, and one of the arguments, infer the length
> of the other. (Oleg provided a solution using FunDeps more than a decade
> ago.) But GHC has special handling for type-level Nats (or rather Ints),
> hence no need to extend injectivity.
>
> Come to that, the original work that delivered Injective Type Families
> failed to find many use cases -- so the motivation was more
> keep-up-with-the-Jones's to provide equivalence to FunDeps.
>
> There were lots of newbie mistakes when Type Families first arrived, of
> thinking they were injective, because a TF application looks like a type
> constructor application `F Int` cp `T Int`. But perhaps that
> misunderstanding didn't represent genuine use cases?
>
> Is anybody out there using Injective Type Families currently? What for?
>
> AntC
>
>
>> On Mon, Nov 20, 2017 at 3:44 AM Anthony Clayden <
>> anthony_clayden at clear.net.nz> wrote:
>>
>>> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>>>
>>> (Moving to ghc-users, there's nothing particularly dev-y.)
>>>
>>> > Sometimes it woulld be useful to be able to reason
>>> backwards
>>> > about type families.
>>>
>>> Hi David, this is a well-known issue/bit of a sore.
>>> Discussed much in the debate between type families
>>> compared to FunDeps.
>>>
>>> > For example, we have
>>> >
>>> > type family a && b where
>>> > 'False && b = 'False
>>> > 'True && b = b
>>> > a && 'False = 'False
>>> > a && 'True = a
>>> > a && a = a
>>>
>>> > ... if we know something about the *result*,
>>> > GHC doesn't give us any way to learn anything about the
>>> arguments.
>>>
>>> You can achieve the improvement you want today.
>>>
>>> You'll probably find Oleg has a solution
>>> With FunDeps and superclass constraints, it'll go like this
>>>
>>> class (OnResult r a b, OnResult r b a) => And a b r | a b ->
>>> r
>>>
>>> instance And 'False b 'False
>>> -- etc, as you'd expect following the tf equations
>>> -- the instances are overlapping but confluent
>>>
>>> class OnResult r a b | r a -> b
>>> instance OnResult 'True a 'True
>>> instance OnResult 'False 'True 'False
>>>
>>> You could equally make `OnResult` a type family.
>>>
>>> If you can trace backwards to where `&&` is used,
>>> you might be able to add suitable constraints there.
>>>
>>> So there's a couple of futures:
>>> * typechecker plugins, using an SMT solver
>>> * injective type families
>>> the next phase is supposed to allow
>>>
>>> type family a && b = r | r a -> b, r b -> a where ...
>>>
>>> That will help with some type families
>>> (such as addition of Nats),
>>> plug1
>>> https://github.com/AntC2/ghc-proposals/blob/instance-
>>> apartness-guards/proposals/0000-instance-apartness-
>>> guards.rst#injective-type-families
>>>
>>> but I don't see it helping here.
>>> plug2 (this example)
>>> https://github.com/AntC2/ghc-proposals/blob/instance-
>>> apartness-guards/proposals/0000-instance-apartness-
>>> guards.rst#type-family-coincident-overlap
>>>
>>> Because (for example) if you unify the first two equations,
>>> (that is, looking for coincident overlap)
>>>
>>> 'False && 'False = 'False
>>> 'True && 'False = 'False
>>>
>>> That's inconsistent on dependency ` r b -> a`.
>>>
>>> And you can't fix it by re-ordering the closed equations.
>>>
>>> > For (&&), the obvious things you'd want are ...
>>> >
>>> > There's nothing inherently impossible about this sort of
>>> reasoning.
>>>
>>> No-ish but. It relies on knowing kind `Bool` is closed.
>>> And GHC doesn't pay attention to that.
>>> So you need to bring type family `Not`
>>> into the reasoning; hence a SMT solver.
>>>
>>> > ...
>>> > I wouldn't necessarily expect GHC
>>> > to be able to work something like this out on its own.
>>>
>>> That's a relief ;-)
>>>
>>> > But it seems like there should be some way to allow the
>>> user
>>> > to guide it to a proof.
>>>
>>> Yes, an SMT solver with a model for kind `Bool`.
>>> (And a lot of hard work to teach it, by someone.)
>>>
>>> AntC
>>> _______________________________________________
>>> Glasgow-haskell-users mailing list
>>> Glasgow-haskell-users at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>>
>>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From anthony_clayden at clear.net.nz Thu Dec 14 01:33:59 2017
From: anthony_clayden at clear.net.nz (Anthony Clayden)
Date: Thu, 14 Dec 2017 01:33:59 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
On Thu, 14 Dec 2017 at 1:55 PM, Clinton Mead
wrote:
> Injective Type Families are at the core of my "Freelude" package, which
> allows many more types to be defined as Categories, Functors, Applicatives
> and Monads.
>
Cool!
> What would also be helpful is if injectivity of type C as mentioned on the
> page ...
>
OK. That's as per the type-level addition of Nats I mentioned. Did you
consider using FunDeps instead of Injective Type Families?
(I see lower down that page, type C is described as 'generalized'
injectivity.)
The variety of injectivity David F's o.p. talked about is orthogonal across
types A, B, C. We might call it 'partial injectivity' as in partial
function:
* some values of the result determine (some of) the arguments; and/or
* some values of the result with some values of some arguments determine
other arguments; but
* for some values of the result and/or some arguments, we can't determine
the other arguments.
You can kinda achieve that now using FunDeps with overlapping instances
with UndecidableInstances exploiting GHC's bogus consistency check on
FunDeps https://ghc.haskell.org/trac/ghc/ticket/10675#comment:15.
Or maybe with (Closed) Type Families if you put a bogus catch-all at the
end of the sequence of equations:
> type family F a where
> ...
> F a = F a
(But then it can't be injective, so you have to stitch it together with
type classes and superclass equality constraints and who-knows-what.)
None of it is sound or complete or rugged, in particular you can't risk
orphan instances -- unless plug3:
https://github.com/ghc-proposals/ghc-proposals/pull/56#issuecomment-351289722
AntC
> On Thu, Dec 14, 2017 at 11:29 AM, Anthony Clayden <
> anthony_clayden at clear.net.nz> wrote:
>
>>
>> On Tue, 12 Dec 2017 at 4:53 PM, Carter Schonwald
>> wrote:
>>
>>> This was / perhaps still is one goal of injective type families too!
>>> I’m not sure why the current status is, but it’s defjnitely related
>>>
>>
>> Thanks Carter, yes this sort of injectiviy (semi-injectivity? partial
>> injectivity?) is noted as future work in the 2015 paper. But I'm not seeing
>> a lot of hollerin' for it(?) Or am I looking in the wrong places?
>>
>> The classic example is for Nats in length-indexed vectors: if we know the
>> length of appending two vectors, and one of the arguments, infer the length
>> of the other. (Oleg provided a solution using FunDeps more than a decade
>> ago.) But GHC has special handling for type-level Nats (or rather Ints),
>> hence no need to extend injectivity.
>>
>> Come to that, the original work that delivered Injective Type Families
>> failed to find many use cases -- so the motivation was more
>> keep-up-with-the-Jones's to provide equivalence to FunDeps.
>>
>> There were lots of newbie mistakes when Type Families first arrived, of
>> thinking they were injective, because a TF application looks like a type
>> constructor application `F Int` cp `T Int`. But perhaps that
>> misunderstanding didn't represent genuine use cases?
>>
>> Is anybody out there using Injective Type Families currently? What for?
>>
>> AntC
>>
>>
>>> On Mon, Nov 20, 2017 at 3:44 AM Anthony Clayden <
>>> anthony_clayden at clear.net.nz> wrote:
>>>
>>>> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>>>>
>>>> (Moving to ghc-users, there's nothing particularly dev-y.)
>>>>
>>>> > Sometimes it woulld be useful to be able to reason
>>>> backwards
>>>> > about type families.
>>>>
>>>> Hi David, this is a well-known issue/bit of a sore.
>>>> Discussed much in the debate between type families
>>>> compared to FunDeps.
>>>>
>>>> > For example, we have
>>>> >
>>>> > type family a && b where
>>>> > 'False && b = 'False
>>>> > 'True && b = b
>>>> > a && 'False = 'False
>>>> > a && 'True = a
>>>> > a && a = a
>>>>
>>>> > ... if we know something about the *result*,
>>>> > GHC doesn't give us any way to learn anything about the
>>>> arguments.
>>>>
>>>> You can achieve the improvement you want today.
>>>>
>>>> You'll probably find Oleg has a solution
>>>> With FunDeps and superclass constraints, it'll go like this
>>>>
>>>> class (OnResult r a b, OnResult r b a) => And a b r | a b ->
>>>> r
>>>>
>>>> instance And 'False b 'False
>>>> -- etc, as you'd expect following the tf equations
>>>> -- the instances are overlapping but confluent
>>>>
>>>> class OnResult r a b | r a -> b
>>>> instance OnResult 'True a 'True
>>>> instance OnResult 'False 'True 'False
>>>>
>>>> You could equally make `OnResult` a type family.
>>>>
>>>> If you can trace backwards to where `&&` is used,
>>>> you might be able to add suitable constraints there.
>>>>
>>>> So there's a couple of futures:
>>>> * typechecker plugins, using an SMT solver
>>>> * injective type families
>>>> the next phase is supposed to allow
>>>>
>>>> type family a && b = r | r a -> b, r b -> a where ...
>>>>
>>>> That will help with some type families
>>>> (such as addition of Nats),
>>>> plug1
>>>>
>>>> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#injective-type-families
>>>>
>>>> but I don't see it helping here.
>>>> plug2 (this example)
>>>>
>>>> https://github.com/AntC2/ghc-proposals/blob/instance-apartness-guards/proposals/0000-instance-apartness-guards.rst#type-family-coincident-overlap
>>>>
>>>> Because (for example) if you unify the first two equations,
>>>> (that is, looking for coincident overlap)
>>>>
>>>> 'False && 'False = 'False
>>>> 'True && 'False = 'False
>>>>
>>>> That's inconsistent on dependency ` r b -> a`.
>>>>
>>>> And you can't fix it by re-ordering the closed equations.
>>>>
>>>> > For (&&), the obvious things you'd want are ...
>>>> >
>>>> > There's nothing inherently impossible about this sort of
>>>> reasoning.
>>>>
>>>> No-ish but. It relies on knowing kind `Bool` is closed.
>>>> And GHC doesn't pay attention to that.
>>>> So you need to bring type family `Not`
>>>> into the reasoning; hence a SMT solver.
>>>>
>>>> > ...
>>>> > I wouldn't necessarily expect GHC
>>>> > to be able to work something like this out on its own.
>>>>
>>>> That's a relief ;-)
>>>>
>>>> > But it seems like there should be some way to allow the
>>>> user
>>>> > to guide it to a proof.
>>>>
>>>> Yes, an SMT solver with a model for kind `Bool`.
>>>> (And a lot of hard work to teach it, by someone.)
>>>>
>>>> AntC
>>>> _______________________________________________
>>>> Glasgow-haskell-users mailing list
>>>> Glasgow-haskell-users at haskell.org
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>>>
>>>
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From david.feuer at gmail.com Thu Dec 14 02:06:34 2017
From: david.feuer at gmail.com (David Feuer)
Date: Wed, 13 Dec 2017 21:06:34 -0500
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To: <5a1295b1.33d.372a.15211@clear.net.nz>
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
I still haven't really digested what you've written, but I wish to pick a
nit (below)
On Nov 20, 2017 3:44 AM, "Anthony Clayden"
wrote:
> On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
...
> For (&&), the obvious things you'd want are ...
>
> There's nothing inherently impossible about this sort of
reasoning.
No-ish but. It relies on knowing kind `Bool` is closed.
And GHC doesn't pay attention to that.
So you need to bring type family `Not`
into the reasoning; hence a SMT solver.
I don't think this is entirely correct. The fact that Bool is closed does
not seem relevant. The key fact, I believe, is that (&&) is closed. Asking
GHC to reason like this about open type families smells much harder, but
maybe my sense of smell is off.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From clintonmead at gmail.com Thu Dec 14 02:57:05 2017
From: clintonmead at gmail.com (Clinton Mead)
Date: Thu, 14 Dec 2017 13:57:05 +1100
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
Hi AntC
I've panicked GHC enough whilst developing Freelude so whilst I'm not sure
exactly what you're saying I'd be hestiant about exploiting anything bogus
(8.2 btw seems far more stable than 8.0 btw).
The trick is teaching GHC to do all the type trickery it needs so you can
write things like:
((f1,g1), Just h1, [x1,x2]) . ((f2,g2), Nothing. [y1,y2,y3])
Under Freelude this should happily compile (assuming all the bits are
categories themselves such as functions). Pairs of categories is a
category, Maybe of a category is a category, and a list of categories is a
category, and finally a triple of categories is a category. So composition
should be defined.
I'm no expert in the GHC type system (I don't really know any type theory
at all) but from what I observed injectivity allows the compiler to "dig"
all the way down this chain whilst still leaving some breadcrumbs to find
it's way back up. It's the two way equivalence that seems to help, GHC can
jump back and forth. I've tried this with non injective type families and
just making "inverse" type families but it just seems to end in tears and a
mass of type mismatches.
Although, I'd love people to look at the code, play with it and suggest
improvements.
Clinton
On Thu, Dec 14, 2017 at 12:33 PM, Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:
>
> On Thu, 14 Dec 2017 at 1:55 PM, Clinton Mead
> wrote:
>
>> Injective Type Families are at the core of my "Freelude" package, which
>> allows many more types to be defined as Categories, Functors, Applicatives
>> and Monads.
>>
>
> Cool!
>
>
>> What would also be helpful is if injectivity of type C as mentioned on
>> the page ...
>>
>
> OK. That's as per the type-level addition of Nats I mentioned. Did you
> consider using FunDeps instead of Injective Type Families?
>
> (I see lower down that page, type C is described as 'generalized'
> injectivity.)
>
> The variety of injectivity David F's o.p. talked about is orthogonal
> across types A, B, C. We might call it 'partial injectivity' as in partial
> function:
> * some values of the result determine (some of) the arguments; and/or
> * some values of the result with some values of some arguments determine
> other arguments; but
> * for some values of the result and/or some arguments, we can't determine
> the other arguments.
>
> You can kinda achieve that now using FunDeps with overlapping instances
> with UndecidableInstances exploiting GHC's bogus consistency check on
> FunDeps https://ghc.haskell.org/trac/ghc/ticket/10675#comment:15.
>
> Or maybe with (Closed) Type Families if you put a bogus catch-all at the
> end of the sequence of equations:
>
> > type family F a where
> > ...
> > F a = F a
>
> (But then it can't be injective, so you have to stitch it together with
> type classes and superclass equality constraints and who-knows-what.)
>
> None of it is sound or complete or rugged, in particular you can't risk
> orphan instances -- unless plug3: https://github.com/ghc-
> proposals/ghc-proposals/pull/56#issuecomment-351289722
>
> AntC
>
>
>> On Thu, Dec 14, 2017 at 11:29 AM, Anthony Clayden <
>> anthony_clayden at clear.net.nz> wrote:
>>
>>>
>>> On Tue, 12 Dec 2017 at 4:53 PM, Carter Schonwald <
>>> redirect at vodafone.co.nz> wrote:
>>>
>>>> This was / perhaps still is one goal of injective type families too!
>>>> I’m not sure why the current status is, but it’s defjnitely related
>>>>
>>>
>>> Thanks Carter, yes this sort of injectiviy (semi-injectivity? partial
>>> injectivity?) is noted as future work in the 2015 paper. But I'm not seeing
>>> a lot of hollerin' for it(?) Or am I looking in the wrong places?
>>>
>>> The classic example is for Nats in length-indexed vectors: if we know
>>> the length of appending two vectors, and one of the arguments, infer the
>>> length of the other. (Oleg provided a solution using FunDeps more than a
>>> decade ago.) But GHC has special handling for type-level Nats (or rather
>>> Ints), hence no need to extend injectivity.
>>>
>>> Come to that, the original work that delivered Injective Type Families
>>> failed to find many use cases -- so the motivation was more
>>> keep-up-with-the-Jones's to provide equivalence to FunDeps.
>>>
>>> There were lots of newbie mistakes when Type Families first arrived, of
>>> thinking they were injective, because a TF application looks like a type
>>> constructor application `F Int` cp `T Int`. But perhaps that
>>> misunderstanding didn't represent genuine use cases?
>>>
>>> Is anybody out there using Injective Type Families currently? What for?
>>>
>>> AntC
>>>
>>>
>>>> On Mon, Nov 20, 2017 at 3:44 AM Anthony Clayden <
>>>> anthony_clayden at clear.net.nz> wrote:
>>>>
>>>>> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>>>>>
>>>>> (Moving to ghc-users, there's nothing particularly dev-y.)
>>>>>
>>>>> > Sometimes it woulld be useful to be able to reason
>>>>> backwards
>>>>> > about type families.
>>>>>
>>>>> Hi David, this is a well-known issue/bit of a sore.
>>>>> Discussed much in the debate between type families
>>>>> compared to FunDeps.
>>>>>
>>>>> > For example, we have
>>>>> >
>>>>> > type family a && b where
>>>>> > 'False && b = 'False
>>>>> > 'True && b = b
>>>>> > a && 'False = 'False
>>>>> > a && 'True = a
>>>>> > a && a = a
>>>>>
>>>>> > ... if we know something about the *result*,
>>>>> > GHC doesn't give us any way to learn anything about the
>>>>> arguments.
>>>>>
>>>>> You can achieve the improvement you want today.
>>>>>
>>>>> You'll probably find Oleg has a solution
>>>>> With FunDeps and superclass constraints, it'll go like this
>>>>>
>>>>> class (OnResult r a b, OnResult r b a) => And a b r | a b ->
>>>>> r
>>>>>
>>>>> instance And 'False b 'False
>>>>> -- etc, as you'd expect following the tf equations
>>>>> -- the instances are overlapping but confluent
>>>>>
>>>>> class OnResult r a b | r a -> b
>>>>> instance OnResult 'True a 'True
>>>>> instance OnResult 'False 'True 'False
>>>>>
>>>>> You could equally make `OnResult` a type family.
>>>>>
>>>>> If you can trace backwards to where `&&` is used,
>>>>> you might be able to add suitable constraints there.
>>>>>
>>>>> So there's a couple of futures:
>>>>> * typechecker plugins, using an SMT solver
>>>>> * injective type families
>>>>> the next phase is supposed to allow
>>>>>
>>>>> type family a && b = r | r a -> b, r b -> a where ...
>>>>>
>>>>> That will help with some type families
>>>>> (such as addition of Nats),
>>>>> plug1
>>>>> https://github.com/AntC2/ghc-proposals/blob/instance-
>>>>> apartness-guards/proposals/0000-instance-apartness-
>>>>> guards.rst#injective-type-families
>>>>>
>>>>> but I don't see it helping here.
>>>>> plug2 (this example)
>>>>> https://github.com/AntC2/ghc-proposals/blob/instance-
>>>>> apartness-guards/proposals/0000-instance-apartness-
>>>>> guards.rst#type-family-coincident-overlap
>>>>>
>>>>> Because (for example) if you unify the first two equations,
>>>>> (that is, looking for coincident overlap)
>>>>>
>>>>> 'False && 'False = 'False
>>>>> 'True && 'False = 'False
>>>>>
>>>>> That's inconsistent on dependency ` r b -> a`.
>>>>>
>>>>> And you can't fix it by re-ordering the closed equations.
>>>>>
>>>>> > For (&&), the obvious things you'd want are ...
>>>>> >
>>>>> > There's nothing inherently impossible about this sort of
>>>>> reasoning.
>>>>>
>>>>> No-ish but. It relies on knowing kind `Bool` is closed.
>>>>> And GHC doesn't pay attention to that.
>>>>> So you need to bring type family `Not`
>>>>> into the reasoning; hence a SMT solver.
>>>>>
>>>>> > ...
>>>>> > I wouldn't necessarily expect GHC
>>>>> > to be able to work something like this out on its own.
>>>>>
>>>>> That's a relief ;-)
>>>>>
>>>>> > But it seems like there should be some way to allow the
>>>>> user
>>>>> > to guide it to a proof.
>>>>>
>>>>> Yes, an SMT solver with a model for kind `Bool`.
>>>>> (And a lot of hard work to teach it, by someone.)
>>>>>
>>>>> AntC
>>>>> _______________________________________________
>>>>> Glasgow-haskell-users mailing list
>>>>> Glasgow-haskell-users at haskell.org
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>>>>
>>>>
>>> _______________________________________________
>>> Glasgow-haskell-users mailing list
>>> Glasgow-haskell-users at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From anthony_clayden at clear.net.nz Thu Dec 14 07:18:15 2017
From: anthony_clayden at clear.net.nz (Anthony Clayden)
Date: Thu, 14 Dec 2017 07:18:15 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
On Thu, 14 Dec 2017 at 3:19 PM, David Feuer wrote:
> I still haven't really digested what you've written, but I wish to pick a
> nit (below)
>
Thanks David. Heh, heh. I think we might be agreeing about the phenomenon,
but picking different nits to 'blame'.
> On Nov 20, 2017 3:44 AM, "Anthony Clayden"
> wrote:
>
> > On Thu Nov 16 01:31:55 UTC 2017, David Feuer wrote:
>
> ...
>
>
>
> > For (&&), the obvious things you'd want are ...
> >
> > There's nothing inherently impossible about this sort of
> reasoning.
>
> No-ish but. It relies on knowing kind `Bool` is closed.
> And GHC doesn't pay attention to that.
> So you need to bring type family `Not`
> into the reasoning; hence a SMT solver.
>
>
> I don't think this is entirely correct. The fact that Bool is closed does
> not seem relevant. The key fact, I believe, is that (&&) is closed.
>
Hmm. I wonder what you think "closed" amounts to?
Equation 1 `'False && b = 'False` is consistent with `[b ~ Foo]`
(unless GHC were to reason about closed kinds)
Equation 2 `'True && b = b ` is consistent with `[b ~ Foo]`
And so on.
The last equation `a && a = a` is consistent with `[a ~ Foo]`.
Furthermore it's *inconsistent* with a putative backwards FunDep ` r a ->
b` on `'False && 'True ~ 'False`.
I think it would be better to omit that equation all together.
Then when your o.p. reasons:
>>> ... we can calculate (Not a || Not b) as 'True for each of these LHSes.
What will it calculate for (Not Foo)?
Asking GHC to reason like this about open type families smells much harder,
> but maybe my sense of smell is off.
>
> Hmm. Your o.p. said
>>> In order for the constraint (a && b) ~ 'True to hold, the type family
application *must have reduced* using one of its equations.
I think that's smelly logic: if you want to reason backwards, then you
can't make assumptions about what "must" have reduced if GHC were
reasoning forward. That is, unless you're expecting GHC to behave like
an SMT solver over closed kinds.
Remember that the logic for selecting Closed Type Family equations
works from top to bottom *ignoring anything known about the result*.
So not only must it have reduced using one of the equations; it must
have rejected equations above the one it selected; and it must have
seen evidence for rejecting them. (It's more complicated than that in
practice: if there's coincident overlap, GHC will pick some equation
eagerly. And your `&&` equations exhibit coincident overlap, apart
from the last.)
If you want it to benefit from something known about the result, you
won't (in general) find the same top-to-bottom sequence helps with
type improvement. With the FunDep inconsistency in your last equation
for `&&`, I suspect that equation-selection will get 'stuck' looking
for evidence to reject earlier equations.
If we do expect GHC to behave like an SMT solver over closed kinds,
then it can reason just as well for an open type family; on the
proviso that it can see all the equations.
For a bit of history: during discussions around Injective Type
Families, one suggestion was to infer injectivity by examining the
equations given -- along the lines you're positing. That was rejected
on grounds the equations might exhibit injectivity 'by accident'. Also
that the programmer might intend injectivity, but their equations be
inconsistent. So it was decided there must be explicit declaration;
and the equations must be consistent with that declaration. No
equations for `&&` could be consistent that way.
AntC
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From anthony_clayden at clear.net.nz Thu Dec 14 10:08:37 2017
From: anthony_clayden at clear.net.nz (Anthony Clayden)
Date: Thu, 14 Dec 2017 10:08:37 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
On Thu, 14 Dec 2017 at 4:13 PM, Clinton Mead
wrote:
>
> I've panicked GHC enough whilst developing Freelude so whilst I'm not sure
> exactly what you're saying I'd be hestiant about exploiting anything bogus
> (8.2 btw seems far more stable than 8.0 btw).
>
;-) Fair enough.
"bogus" is SPJ's way of saying: it works, but it isn't supported by deep
type theory. 'C'est brutal mais ca marche.'
And that particular exploit has been stable since 2004 at least: the HList
library totally relied on it until Closed Type Families arrived.
AntC
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From clintonmead at gmail.com Thu Dec 14 13:05:42 2017
From: clintonmead at gmail.com (Clinton Mead)
Date: Thu, 14 Dec 2017 13:05:42 +0000
Subject: [was ghc-devs] Reasoning backwards with type families
In-Reply-To:
References: <5a1295b1.33d.372a.15211@clear.net.nz>
Message-ID:
Happy to go with the bogusness if it works better than injective types,
feel free to submit a patch. :)
On Thu, 14 Dec 2017 at 9:08 pm, Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:
> On Thu, 14 Dec 2017 at 4:13 PM, Clinton Mead
> wrote:
>
>>
>> I've panicked GHC enough whilst developing Freelude so whilst I'm not
>> sure exactly what you're saying I'd be hestiant about exploiting anything
>> bogus (8.2 btw seems far more stable than 8.0 btw).
>>
>
> ;-) Fair enough.
>
> "bogus" is SPJ's way of saying: it works, but it isn't supported by deep
> type theory. 'C'est brutal mais ca marche.'
>
> And that particular exploit has been stable since 2004 at least: the HList
> library totally relied on it until Closed Type Families arrived.
>
> AntC
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From juhpetersen at gmail.com Fri Dec 15 04:37:25 2017
From: juhpetersen at gmail.com (Jens Petersen)
Date: Fri, 15 Dec 2017 13:37:25 +0900
Subject: [ANNOUNCE] GHC 8.2.2 released
In-Reply-To: <878tezfg1u.fsf@ben-laptop.smart-cactus.org>
References: <878tezfg1u.fsf@ben-laptop.smart-cactus.org>
Message-ID:
On 22 November 2017 at 07:00, Ben Gamari wrote:
> The Glasgow Haskell Compiler -- version 8.2.2
Thanks, I have finally built it for current Fedora releases and EPEL7
in my Copr repo:
https://copr.fedorainfracloud.org/coprs/petersen/ghc-8.2.2
Jens
From ben at well-typed.com Wed Dec 20 20:48:00 2017
From: ben at well-typed.com (Ben Gamari)
Date: Wed, 20 Dec 2017 15:48:00 -0500
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
Message-ID: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
The GHC development team is pleased to announce the first alpha release
of the 8.4.1 release. The usual release artifacts are available from
https://downloads.haskell.org/~ghc/8.4.1-alpha1
Note that this release drops compatibility with GCC 4.6 and earlier.
While we generally try to place as few constraints on system toolchain
as possible, this release depends upon the __atomic__ builtins provided
by GCC 4.7 and later (see #14244).
=== Notes on release scheduling ===
The 8.4.1 release marks the first release where GHC will be adhering to
its new, higher-cadence release schedule [1]. Under this new scheme,
major releases will be made in 6-month intervals with interstitial minor
releases as necessary.
In order to minimize the likelihood of schedule slippage and to ensure
adequate testing, each major release will be preceeded by a number of
regular alpha releases. We will begin issuing these releases roughly
three months before the final date of the major release and will issue
roughly one every two weeks during this period. This high release
cadence will allow us to quickly get fixes in to users hands and allow
better feedback on the status of the release.
GHC 8.4 is slated to be released in mid-February but, due to technical
constraints, we are starting the alpha-release cycle a bit later than
planned under the above schedule. For this reason, it would be greatly
appreciated if users could put this alpha through its paces to make up
for lost time.
As always, do let us know if you encounter any trouble in the course of
testing. Thanks for your help!
Cheers,
- Ben
[1] https://ghc.haskell.org/trac/ghc/blog/2017-release-schedule
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL:
From george.colpitts at gmail.com Thu Dec 21 20:16:01 2017
From: george.colpitts at gmail.com (George Colpitts)
Date: Thu, 21 Dec 2017 20:16:01 +0000
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
In-Reply-To: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
References: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
Message-ID:
Thanks Ben. I installed the Mac binaries.
For others who are wondering, you need llvm 5 if you want to use llvm with
this.
Needless to say, many libraries, e.g. haskell-src-exts, primitive, and
intero won't compile with this even with --allow-newer
I'll notify those libraries about that in case they want to get started on
8.4.1
Cheers
George
On Wed, Dec 20, 2017 at 4:48 PM Ben Gamari wrote:
>
> The GHC development team is pleased to announce the first alpha release
> of the 8.4.1 release. The usual release artifacts are available from
>
> https://downloads.haskell.org/~ghc/8.4.1-alpha1
>
> Note that this release drops compatibility with GCC 4.6 and earlier.
> While we generally try to place as few constraints on system toolchain
> as possible, this release depends upon the __atomic__ builtins provided
> by GCC 4.7 and later (see #14244).
>
>
> === Notes on release scheduling ===
>
> The 8.4.1 release marks the first release where GHC will be adhering to
> its new, higher-cadence release schedule [1]. Under this new scheme,
> major releases will be made in 6-month intervals with interstitial minor
> releases as necessary.
>
> In order to minimize the likelihood of schedule slippage and to ensure
> adequate testing, each major release will be preceeded by a number of
> regular alpha releases. We will begin issuing these releases roughly
> three months before the final date of the major release and will issue
> roughly one every two weeks during this period. This high release
> cadence will allow us to quickly get fixes in to users hands and allow
> better feedback on the status of the release.
>
> GHC 8.4 is slated to be released in mid-February but, due to technical
> constraints, we are starting the alpha-release cycle a bit later than
> planned under the above schedule. For this reason, it would be greatly
> appreciated if users could put this alpha through its paces to make up
> for lost time.
>
> As always, do let us know if you encounter any trouble in the course of
> testing. Thanks for your help!
>
> Cheers,
>
> - Ben
>
>
> [1] https://ghc.haskell.org/trac/ghc/blog/2017-release-schedule
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From george.colpitts at gmail.com Fri Dec 22 13:22:12 2017
From: george.colpitts at gmail.com (George Colpitts)
Date: Fri, 22 Dec 2017 13:22:12 +0000
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
In-Reply-To:
References: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
Message-ID:
Probably stating what is obvious and well-know but anyways:
- On the status page
it would be
good to have a link for "Phase 2 of the Semigroup-Monoid Proposal (Herbert
Riedel)"
- Also IIRC we normally have a page on porting to the new release. It
would be good to have that also when we have a chance.
It's great that we are getting started early.
On Thu, Dec 21, 2017 at 4:16 PM George Colpitts
wrote:
> Thanks Ben. I installed the Mac binaries.
>
> For others who are wondering, you need llvm 5 if you want to use llvm with
> this.
>
> Needless to say, many libraries, e.g. haskell-src-exts, primitive, and
> intero won't compile with this even with --allow-newer
>
> I'll notify those libraries about that in case they want to get started on
> 8.4.1
>
> Cheers
> George
>
> On Wed, Dec 20, 2017 at 4:48 PM Ben Gamari wrote:
>
>>
>> The GHC development team is pleased to announce the first alpha release
>> of the 8.4.1 release. The usual release artifacts are available from
>>
>> https://downloads.haskell.org/~ghc/8.4.1-alpha1
>>
>> Note that this release drops compatibility with GCC 4.6 and earlier.
>> While we generally try to place as few constraints on system toolchain
>> as possible, this release depends upon the __atomic__ builtins provided
>> by GCC 4.7 and later (see #14244).
>>
>>
>> === Notes on release scheduling ===
>>
>> The 8.4.1 release marks the first release where GHC will be adhering to
>> its new, higher-cadence release schedule [1]. Under this new scheme,
>> major releases will be made in 6-month intervals with interstitial minor
>> releases as necessary.
>>
>> In order to minimize the likelihood of schedule slippage and to ensure
>> adequate testing, each major release will be preceeded by a number of
>> regular alpha releases. We will begin issuing these releases roughly
>> three months before the final date of the major release and will issue
>> roughly one every two weeks during this period. This high release
>> cadence will allow us to quickly get fixes in to users hands and allow
>> better feedback on the status of the release.
>>
>> GHC 8.4 is slated to be released in mid-February but, due to technical
>> constraints, we are starting the alpha-release cycle a bit later than
>> planned under the above schedule. For this reason, it would be greatly
>> appreciated if users could put this alpha through its paces to make up
>> for lost time.
>>
>> As always, do let us know if you encounter any trouble in the course of
>> testing. Thanks for your help!
>>
>> Cheers,
>>
>> - Ben
>>
>>
>> [1] https://ghc.haskell.org/trac/ghc/blog/2017-release-schedule
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
From ben at well-typed.com Fri Dec 22 17:08:47 2017
From: ben at well-typed.com (Ben Gamari)
Date: Fri, 22 Dec 2017 12:08:47 -0500
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
In-Reply-To:
References: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
Message-ID: <871sjmd71h.fsf@ben-laptop.smart-cactus.org>
George Colpitts writes:
> Probably stating what is obvious and well-know but anyways:
>
> - On the status page
> it would be
> good to have a link for "Phase 2 of the Semigroup-Monoid Proposal (Herbert
> Riedel)"
Good catch. I've added a link.
> - Also IIRC we normally have a page on porting to the new release. It
> would be good to have that also when we have a chance.
>
Indeed, the migration page can be found here:
https://ghc.haskell.org/trac/ghc/wiki/Migration/8.4. I've added a link
to the 8.4 status page.
Cheers,
- Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL:
From manny at fpcomplete.com Fri Dec 29 17:58:56 2017
From: manny at fpcomplete.com (Emanuel Borsboom)
Date: Fri, 29 Dec 2017 09:58:56 -0800
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
In-Reply-To:
References: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
Message-ID: <063D5643-88A7-4776-8C58-8662B420588A@fpcomplete.com>
Hi Ben,
Are there any plans to start releasing Linux bindists linked with libncurses.so.6? A number of Linux distributions have upgraded from 5, including Fedora, Arch and Gentoo, and the currently available official bindists don't work out of the box on those anymore.
-- Manny
From ben at well-typed.com Sun Dec 31 05:19:26 2017
From: ben at well-typed.com (Ben Gamari)
Date: Sun, 31 Dec 2017 00:19:26 -0500
Subject: [ANNOUNCE] GHC 8.4.1-alpha1 available
In-Reply-To: <063D5643-88A7-4776-8C58-8662B420588A@fpcomplete.com>
References: <87bmitcejz.fsf@ben-laptop.smart-cactus.org>
<063D5643-88A7-4776-8C58-8662B420588A@fpcomplete.com>
Message-ID: <87d12vbhk3.fsf@ben-laptop.smart-cactus.org>
Emanuel Borsboom writes:
> Hi Ben,
>
> Are there any plans to start releasing Linux bindists linked with
> libncurses.so.6? A number of Linux distributions have upgraded from 5,
> including Fedora, Arch and Gentoo, and the currently available
> official bindists don't work out of the box on those anymore.
>
Indeed I can add an ncurses.so.6 platform to the build matrix. I'll
start with the next alpha. Thanks for mentioning this!
Cheers,
- Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL: