Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,265
    • Issues 4,265
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 419
    • Merge Requests 419
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #3108

Closed
Open
Opened Mar 18, 2009 by Simon Peyton Jones@simonpjDeveloper

Do a better job of solving recursive type-class constraints with functional dependencies

This ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints: http://www.haskell.org/pipermail/haskell/2009-March/021115.html. We might want to get back to this when the new constraint solver is in place.

The question concerns the interaction of solving recursive type-class constraints, where it is important to aggressively apply functional dependencies. Here's Tom Schrijvers's analysis of Ralf's example:

"The cyclic dictionaries approach is a bit fragile. The problem appears to be here that GHC alternates exhaustive phases of constraint reduction and functional dependency improvement. The problem is that in your example you need both for detecting a cycle.

This can happen:

        C1 Int
        ==> 3rd C1 inst
        C2 Int y, C1 (y,Bool)
        ==> 1st C1 inst
        C2 Int y, C1 y, C1 Bool
        ==> 2nd C1 inst
        C2 Int y, C1 y
        ==> 3rd C1 inst
        C2 Int y, C2 y z, C1 (z,Bool)
        ==>
        ...

where all the constraint are different because fresh variables are introduced.

What you want to happen is:

        C1 Int
        ==> 3rd C1 inst
        C2 Int y, C1 (y,Bool)
        ==> 1st C1 inst
        C2 Int y, C1 y, C1 Bool
        ==> 2nd C1 inst
        C2 Int y, C1 y
        ==> C2 FD improvement {Int/y}  <<<<
        C2 Int Int, C1 Int
        ==> C1 Int cycle detected
        C2 Int Int
        ==> C2 1st instance
        {}

It seems that you want improvement to happen at a higher priority than GHC does now."

Trac metadata
Trac field Value
Version 6.10.1
Type Bug
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component Compiler (Type checker)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
Assignee
Assign to
7.6.1
Milestone
7.6.1
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#3108