For a project I did a while ago, I also had a similar blacklist on valid hole fits. Not all of these should be in GHC, and it didn't include some of the examples above, but I figured seeing these might be useful to someone implementing this. All functions below showed up at some point in irrelevant suggestions.

For normal hole fits, I filtered: [ "otherwise" -- is True , "return" -- is pure , "<$>" , "seq" , "const" -- pure is const , "minBound" , "maxBound" , "pi" , "$!" , "negate" , "succ" , "fromEnum" , "toEnum" , "abs" , "signum" , "subtract" , "div" , "pred" , "mod" , "gcd" , "lcm" , "quot" , "rem" , "max" , "min" , "fromIntegral" , "fail" ]

For 'refinement hole fits', the blacklist added these options: [ "id" , "head" , "last" , "tail" , "init" , "foldl1" , "foldl'" , "foldl1'" , "foldr1" , "maximum" , "minimum" , "maximumBy" , "minimumBy" , "!!" , "$" , "read" , "unsafePerformIO" , "asTypeOf" ]

Note that most of the functions in the latter list are to avoid refinement suggestions like "head []".

@Tritlo I wrote a `prototype' over at https://github.com/jippiedoe/Recursively-finding-valid-hole-fits. Some notes: Although technically the plugin feature is 'up to the task', there are definitely shortcomings. A bunch of code from TcHoleErrors had to be copy-pasted as it's only local, the holes I find can't be zonked because zonking happens before the FitPlugin and the environment isn't passed on. I also found a bug in the mean time (#16962), and some small (style) inconsistencies in TcHoleErrors that weren't worth addressing when I wasn't working in ghc to begin with. Despite all this, once I understood the code this was a fairly easy task and the plugin has a very modest amount of code, while supporting a couple of features and configurings. Depending on the settings, it also performs a lot faster than I expected. All in all, I feel like it might be worth reconsidering implementing this functionality in GHC?

I just noticed that this problem only occurs in refinement hole fits:
`(Leaf f) <*> x = _ f x`

works just fine and suggests fmap.

Hole fits don't include suggestions from other (prerequisite) typeclasses.

```
module Typeclasses where
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving (Eq,Show)
instance Functor Tree where
fmap f (Leaf a) = Leaf $ f a
fmap f (Node a b) = Node (fmap f a) (fmap f b)
instance Applicative Tree where
pure = Leaf
(Leaf f) <*> x = _ --fmap f x
(Node f g) <*> x = Node (f <*> x) (g <*> x)
```

Compiled with `ghc tests/Typeclasses.hs -frefinement-level-hole-fits=3 -fno-max-refinement-hole-fits`

Suggests `Leaf, (<*>), Node, pure, id, head, last, asTypeOf, (!!)`

Since `fmap f x`

or `f <$> x`

is typecorrect, I would expect it to show up. Both because fmap for Tree is defined above, and because Functor is a prerequisite of Applicative.

- GHC version used: Glasgow Haskell Compiler, Version 8.9.0.20190705, stage 2 booted by GHC version 8.6.5

Ah, thank you! I was busy getting familiar with ghc but hadn't deciphered those yet. I will definitely do that! I'll get back to you with how successful this project is going.

Very similar to the motivation of finding valid hole fits in the first place, this feature is also inspired by Agda's autofill feature. This approach has two obvious, and impactful, differences in user experience to the current approach:

- The suggestions will be more informative and helpful to, what I presume to be, the target audience of these messages.
- The required time to calculate these suggestions will massively increase.

I'm not trying to understate this downside, this feature would definitely be off by default. The main use could be found in IDE's, that can find these suggestions in the background, but asking for these suggestions through the commandline is also reasonable.

The suggestions will not be as useful as in Agda, where the dependant types often steer the program even more, but can be very useful for writing for example instances of typeclasses.

(I have recently done a group project where we implemented exactly this, for a minimal toy language. In that language, we found that a type signature and one or two test cases were often enough to ensure that the hole fit that passed the tests had the correct definition for simple funtions like length, sum, product, etc.)

Using a form of breadth-first search to recursively find valid fits for typed holes, that may consist of an application of multiple functions. Ideally this could be implemented purely by calling the current implementation of hole fits and refinement holes.

`instance Functor Tree where`

```
fmap f (Leaf a) = _
fmap f (Node a b) = _
```

(...)

`instance Traversable Tree where`

```
traverse f (Leaf a) = _
traverse f (Node a b) = _
```

The idea is that ghc could generate the "least complicated" typecorrect solutions to these holes, and the appropriate solution should be in the top few results. "Least complicated" here is defined by the number of funtions, which corresponds to the depth in our search tree.

I'm very interested in implementing this feature myself, but would like to hear your thoughts about it.