1 
import qualified Prelude

class List list where
  toList :: list a -> [a]
  fromList :: [a] -> list a

data Deque a = Deque [a] [a]

instance List Deque where
  toList (Deque xs sy) = xs ++ reverse sy

  fromList xs = Deque ys (reverse zs)
    where (ys, zs) = splitAt (length xs `div` 2) xs

I am getting an error as copied below. It seems that GHCI does not detect ys as a Deque, and instead as a general instance of class List.

ghci> xs = [2, 3, 4]
ghci> ys = fromList xs
ghci> (Deque a b) = ys
ghci> toList (Deque a b)
[2,3,4]
ghci> toList ys

<interactive>:5:1: error:
    * Could not deduce (List list0) arising from a use of `toList'
      from the context: Num a
        bound by the inferred type of it :: Num a => [a]
        at <interactive>:5:1-9
      The type variable `list0' is ambiguous
      These potential instance exist:
        instance [safe] List Deque -- Defined at main.hs:12:10
    * In the expression: toList ys
      In an equation for `it': it = toList ys
Improve this question
1
  • fromList xs = Deque xs []. Presumably, your deque functions already handle rebalancing the two underlying lists: there's no need to duplicate that in your List instance. Commented Jan 4, 2022 at 23:18

2 Answers 2

Reset to default
6 
ghci> let xs = [2, 3, 4]
ghci> let ys = fromList ys

At this point the values have the most general type possible:

ghci> :t xs
xs :: Num a => [a]
ghci> :t ys
ys :: (List list, Num a) => list a

No hint of a Deque, which makes sense because you haven't mentioned any deques yet.

But those variables stay the same, and they won't change their type!

So after

ghci> (Deque a b) = ys
ghci> toList (Deque a b)
[2,3,4]

you still have the same situation for ys, i.e.

ghci> :t ys
ys :: (List list, Num a) => list a

Sure, you have used ys as a deque once, which is one way it can be used. But being polymorphic, it can just as well be any other List type, and GHCi won't make any guesses which it is supposed to be. But you can of course just tell it:

ghci> toList (ys :: Deque Int)
[2,3,4]

Or shorter

ghci> :set -XTypeApplications 
ghci> toList @Deque ys
[2,3,4]
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

This is working as designed. When you write:

λ> ys = fromList xs

the type assigned to ys is:

λ> :t ys
ys :: (List list, Prelude.Num a) => list a

That is, ys is a polymorphic value that can "be" any sort of List.

So, when you bind it to a particular pattern:

λ> Deque a b = ys

then ys is instantiated as a Deque and appropriate values are bound to a and b, but this doesn't make ys monomorphic. That is, ys hasn't suddenly "become" a Deque. Instead, it remains a polymorphic value that can be rebound to some other List. For example, if you also had an instance for plain old lists:

instance List [] where
  toList = id
  fromList = id

you could instantiate ys at multiple types:

λ> xs = [2, 3, 4]
λ> ys = fromList xs
λ> Deque a b = ys     -- instantiate as Deque
λ> c:d = ys           -- instantiate as []

If this strikes you as odd, consider that:

λ> id "hello"
λ> id 'x'

both work, even though the first time the polymorphic value id :: a -> a is used, it's instantiated as String -> String, while the second time it's used, it's instantiated as Char -> Char. It's the same principle.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.