Trying to understanding why this function using foldr in Haskell isnt working

Question

So I'm new to Haskell and learning it using WikiBooks. And in the higher order functions chapter, there is the following example used.

echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

So I tried running it, but it gives me an error as follows :

 * Ambiguous type variable `t0' arising from a use of `foldr'
  prevents the constraint `(Foldable t0)' from being solved.
  Relevant bindings include
    echoes :: t0 Int -> [Int] (bound at HavingFun.hs:107:1)
  Probable fix: use a type annotation to specify what `t0' should be.
  These potential instances exist:
    instance Foldable (Either a) -- Defined in `Data.Foldable'
    instance Foldable Maybe -- Defined in `Data.Foldable'
    instance Foldable ((,) a) -- Defined in `Data.Foldable'
    ...plus one other
    ...plus 29 instances involving out-of-scope types
    (use -fprint-potential-instances to see them all)
* In the expression: foldr (\ x xs -> (replicate x x) ++ xs) []
  In an equation for `echoes':
      echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

And then if I write it as follows, it works.

echoes lis = foldr (\ x xs -> (replicate x x) ++ xs) [] lis

I am confused about this and I think this is somehow related point free definitions of functions ? Please clarify what the problem is there here. The link from where I'm learning - https://en.wikibooks.org/wiki/Haskell/Lists_III

Answer 1

tl;dr

just always write explicit type signatures, then you're safe(r) from weird problems like that.

---

The reason this used to work but now doesn't is that foldr formerly had the signature

foldr :: (a -> b -> b) -> b -> [a] -> b

which is what the WikiBooks assumes, but in newer GHC it actually has the strictly more general signature

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

The old version is a special case of this, by simply choosing t ~ []. The reason they changed it is that you can also fold over other containers, such as arrays or maps. In fact, in your code

echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

there's nothing the requires the input container to be a list, either, so it would in fact work perfectly well with the signature

echoes :: Foldable t => t Int -> [Int]

...of which, again, [Int] -> [Int] is a special case, so that function could then be used as

> echoes [1,2,3]
[1,2,2,3,3,3]

but also as

> echoes $ Data.Map.fromList [('a',2), ('c',5), ('b',1)]
[2,2,1,5,5,5,5,5]

Or you could have given the function the list-specific signature

echoes' :: [Int] -> [Int]
echoes' = foldr (\x xs -> (replicate x x) ++ xs) []

That works just the same on [1,2,3] but can't accept a Map.

The question is now, why does GHC not infer either of those signatures by itself? Well, if it had to choose one, it should be the more general Foldable version, because people might need to use this with other containers and wouldn't want to keep repeating the Foldable t => quantifier. However, this contradicts another Haskell rule, the monomorphism restriction. Because your echoes implementation doesn't explicitly accept any parameters (it only does that point-freely), it is a constant applicative form, and a standalone CAF is supposed to have monomorphic type unless explicitly specified to be polymorphic. Thus the error message you ran into: GHC really wants this to be monomorphic, but it has no information that restricts what concrete Foldable container to pick.

There are four ways around this:

• As you noticed, by bringing the argument explicitly in scope, echoes is not a CAF anymore and therefore GHC infers the polymorphic type:

  echoes'' l = foldr (\x xs -> (replicate x x) ++ xs) [] l
  

  > :t echoes''
  echoes'' :: Foldable t => t Int -> [Int]

• By disabling the monomorphism restriction, GHC won't care anymore whether it's CAF and just give it the more general type regardless:

  {-# LANGUAGE NoMonomorphismRestriction #-}
  echoes''' = foldr (\x xs -> (replicate x x) ++ xs) []
  

  > :t echoes'''
  echoes''' :: Foldable t => t Int -> [Int]

• Discouraged If you turn on the -XExtendedDefaultingRules extension, GHC will automatically choose [] as the concrete monomorphic container for the CAF:

  {-# LANGUAGE ExtendedDefaultRules #-}
  echoes'''' = foldr (\x xs -> (replicate x x) ++ xs) []
  

  > :t echoes''''
  echoes'''' :: [Int] -> [Int]

  GHCi has -XExtendedDefaultingRules enabled by default, so that's what also happens if you just declare the function in the GHCi prompt.

• Strongly recommended If you explicitly specify the signature, you and GHC both know exactly what's intended and behave accordingly, without requiring any special GHC extensions.

  echoes :: Foldable t => t Int -> [Int]
  echoes = foldr (\x xs -> (replicate x x) ++ xs) []
  
  echoes' :: [Int] -> [Int]
  echoes' = foldr (\x xs -> (replicate x x) ++ xs) []
  

  > :t echoes
  echoes :: Foldable t => t Int -> [Int]
  > :t echoes'
  echoes' :: [Int] -> [Int]