Point-free version produces "Could not match constrained type"

[cscalfani]

Description

I'm not sure if this is a compiler bug, my misunderstanding or a known limitation. I didn't know where else to put this problem, so I'm putting it here hoping I don't waste people's time.

The point-free version of the code under To Reproduce generates a compiler error whereas the non-point-free version compiles no problems.

To Reproduce

Place the following code in a file (Note the Applicative Instance):

module ParserBug where

import Prelude

import Data.Either (Either(..))
import Data.Generic.Rep (class Generic)
import Data.Generic.Rep.Show (genericShow)
import Data.Tuple (Tuple(..))

type ParserState a = Tuple String a

class ParserError e where
  eof :: e

data ParseError
  = EOF
derive instance genericParseError :: Generic ParseError _

instance showParseError :: Show ParseError where
  show = genericShow

instance parserErrorParseError :: ParserError ParseError where
  eof = EOF

type ParserFunction e a = ParserError e => String -> Either e (ParserState a)

data Parser e a = Parser (ParserFunction e a)

instance functorParser :: Functor (Parser e) where
  map f (Parser g) = Parser \s -> map f <$> (g s)

instance applyParser :: Apply (Parser e) where
  apply p1 p2 = Parser \s -> do
    Tuple s1 h <- parse p1 s
    Tuple s2 x <- parse p2 s1
    pure $ Tuple s2 $ h x

instance applicativeParser :: Applicative (Parser e) where
  -- pure x = Parser $ const $ Right $ Tuple "" x -- COMPILES
  pure = Parser <<< const <<< Right <<< Tuple "" -- COMPILER ERROR!!

parse :: ∀ e a. ParserError e => Parser e a -> ParserFunction e a
parse (Parser f) = f

Expected behavior

That the point-free version would compile.

Additional context

N/A

PureScript version

0.13.6

[hdgarrood]

I agree that this probably shouldn't result in a compiler error. I've reproduced this in v0.13.8 too.

[natefaubion]

I think the error is expected. It's a similar issue to https://discourse.purescript.org/t/on-partial-and-composition/1500. Under the point-free code it's not clear where you would insert the constraint elaboration for ParserError e. Making it compile would amount to the compiler eta-expanding the code for you (which we don't do in general).

[hdgarrood]

Ah right okay, yeah, I didn't spot the higher-rank type of the Parser constructor at first.

[cscalfani]

Thanks for the link, @natefaubion. It's a really good explanation.

But seems that Eta-expansion could be done in a simple point-free case like this one pretty easily, e.g.:

g <<< h <<< r <<< s
-- expands to
\x -> g $ h $ r $ s x

Or if there are some efficiency concerns, then maybe this would only be done when there are higher-rank types involved since that's what the programmer is going to have to do anyway.

Just a thought .

[natefaubion]

Eta-expansion can have a pretty drastic effect on evaluation in a strict language. For example, at one point we had an optimization that accidentally eta-expanded point-free compositions, changing the termination properties of the code, while also making it less efficient due to curried arguments not being shared. It is not a goal of the compiler to accept as many possible programs as possible, by for example looking specifically at a chain of simple point-free compositions. Implicitly eta-expanding requires making a lot of assumptions that aren't always a good choice, and so we prefer to not make them on the user's behalf.

[cscalfani]

I'm not surprised that this problem was more nuanced than I was aware of. But since we're going to live with this situation, perhaps a better error message would be warranted to avoid every new PureScript developer going through a similar process.

[natefaubion]

I'm not sure how to make it better, honestly. Eta-expansion is not a universal solution to Could not match constrained type.

[cscalfani]

I've only seen Could not match constrained type in this situation, but maybe simply adding some text to note that this error can SOMETIMES be seen when writing point-free code and try to eta-expand it if that's the case.

IIRC, I've seen an error message that refers to a web page. Not sure if it was in PureScript or Haskell. But that might be a better solution because it doesn't limit the explanation.

[hdgarrood]

I think adding an error page for this error in https://github.com/purescript/documentation/tree/master/errors and linking to (or possibly reproducing) Nate's post on Discourse would help. It looks like we don't have an error page for that exact error code right now.

On Thu, 16 Jul 2020, at 23:29, Charles Scalfani wrote:

I've only seen Could not match constrained type in this situation, but maybe simply adding some text to note that this error can SOMETIMES be seen when writing point-free code and try to eta-expand it if that's the case.

IIRC, I've seen an error message that refers to a web page. Not sure if it was in PureScript or Haskell. But that might be a better solution because it doesn't limit the explanation.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/purescript/purescript/issues/3912#issuecomment-659710136, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAJWDKUGXBJGGRJR6WTFDTLR355OFANCNFSM4O3BA62A.

[cscalfani]

If this is done, I'd suggest copying Nate's explanation just in case the Discourse thread gets archived or deleted.

On Thu, Jul 16, 2020 at 3:33 PM Harry Garrood [email protected] wrote:

I think adding an error page for this error in https://github.com/purescript/documentation/tree/master/errors and linking to (or possibly reproducing) Nate's post on Discourse would help. It looks like we don't have an error page for that exact error code right now.

On Thu, 16 Jul 2020, at 23:29, Charles Scalfani wrote:

I've only seen Could not match constrained type in this situation, but maybe simply adding some text to note that this error can SOMETIMES be seen when writing point-free code and try to eta-expand it if that's the case.

IIRC, I've seen an error message that refers to a web page. Not sure if it was in PureScript or Haskell. But that might be a better solution because it doesn't limit the explanation.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub < https://github.com/purescript/purescript/issues/3912#issuecomment-659710136>, or unsubscribe < https://github.com/notifications/unsubscribe-auth/AAJWDKUGXBJGGRJR6WTFDTLR355OFANCNFSM4O3BA62A .

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/purescript/purescript/issues/3912#issuecomment-659711519, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAFWIQJQIZEYDPU4W23MBNLR3553DANCNFSM4O3BA62A .

-- Charles Scalfani

In The System http://www.amazon.com/dp/B004Q7CH9K (Published Book) Solitary Movie http://www.amazon.com/Solitary-Amber-Jaeger/dp/B004I654WG/ref=sr_1_1?s=dvd&ie=UTF8&qid=1301416276&sr=1-1 (DVD of Produced Screenplay)

http://outputmind.tumblr.com (Random Thoughts Blog) http://blindmansdoubt.tumblr.com (Poetry Blog) http://100milliondollarlotteryquestion.blogspot.com (Wisdom Blog) http://blindmansdoubt.blogspot.com (Poetry Blog Mirror) http://whatyouthinkitisnot.blogspot.com (Short Story Blog)

http://www.linkedin.com/in/cscalfani

[natefaubion]

I think an example in the docs repo is the best thing. This error is a general unification error against a constrained type. For example:

module Main where
data Proxy a = Proxy
class Foo
test :: Proxy (Foo => Int)
test = Proxy :: _ Int

Will trigger it, and there's no amount of eta-expanding to fix it, the type is just wrong to the compiler. I know that sounds pedantic, but I don't think we should add suggestions hoping it might fix it. Saying Try eta-expanding your code isn't really a good suggestions because the user needs to know what it means, and also know exactly where to eta-expand it which isn't always clear. There's just a lot of context necessary.

[cscalfani]

While this case is certainly a case where you've just made a mistake, that doesn't preclude another example in the docs to explain a case where eta-expansion is the solution.

On Thu, Jul 16, 2020 at 3:40 PM Nathan Faubion [email protected] wrote:

I think an example in the docs repo is the best thing. This error is a general unification error against a constrained type. For example:

module Main whereimport Preludedata Proxy a = Proxyclass Footest :: Proxy (Foo => Int) test = Proxy :: _ Int

Will trigger it, and there's no amount of eta-expanding to fix it, the type is just wrong to the compiler. I know that sounds pedantic, but I don't think we should add suggestions hoping it might fix it. Saying Try eta-expanding your code isn't really a good suggestions because the user needs to know what it means, and also know exactly where to eta-expand it which isn't always clear. There's just a lot of context necessary.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/purescript/purescript/issues/3912#issuecomment-659714455, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAFWIQPRVSOF3SGFDVRNZGDR356XTANCNFSM4O3BA62A .

-- Charles Scalfani

In The System http://www.amazon.com/dp/B004Q7CH9K (Published Book) Solitary Movie http://www.amazon.com/Solitary-Amber-Jaeger/dp/B004I654WG/ref=sr_1_1?s=dvd&ie=UTF8&qid=1301416276&sr=1-1 (DVD of Produced Screenplay)

http://outputmind.tumblr.com (Random Thoughts Blog) http://blindmansdoubt.tumblr.com (Poetry Blog) http://100milliondollarlotteryquestion.blogspot.com (Wisdom Blog) http://blindmansdoubt.blogspot.com (Poetry Blog Mirror) http://whatyouthinkitisnot.blogspot.com (Short Story Blog)

http://www.linkedin.com/in/cscalfani