Reputation: 17202
I'm attempting to create a method in Haskell which I would think is very intuitive. I have a list of lists [of lists]* that is arbitrarily deep. I'd like to pull out a specific atom in the list regardless of the depth of the recursion. Here's my effort:
type List = [Array]
data Array = Int | List
drill :: Array -> [Int] -> Array
drill xs (index:[]) = xs !! index
drill xs (index:is) = drill (xs !! index) is
However I receive the following when loading in ghci:
drill.hs:5:23:
Couldn't match expected type `[Array]' with actual type `Array'
In the first argument of `(!!)', namely `xs'
In the expression: xs !! index
In an equation for `drill': drill xs (index : []) = xs !! index
What I've written seems intuitive to me but clearly Haskell is having type issues. And as a Haskell newbie, I'm not the best at interpreting type errors. I would think that the return type of the function could be either an atom: Int
, or a list:[Int]
. Can anybody help me decipher this and suggest a solution?
Upvotes: 1
Views: 267
Reputation: 40797
When you say
data Array = Int | List
this doesn't mean "any Int
is an Array
, and any List
is an Array
". It instead means that Array
has two constructors, Int
and List
, both of which take no arguments. The confusion arises from the fact that they have the same name as types; they're not related to the types beyond sharing a name. That is, your declaration is basically the same as
data Array = Foo | Bar
Instead, we need to give explicit constructor names for each alternative:
type List = [Array]
data Array = Elem Int | Nest List
drill :: Array -> [Int] -> Array
drill xs [] = xs
drill (Nest xs) (index:is) = drill (xs !! index) is
This means that Elem
takes an Int
and returns an Array
, and Nest
takes a List
and returns an Array
. We have to adjust the drill
function to explicitly take the list of Arrays
out of the Nest
case.
The error you're getting is basically saying that you're trying to use xs
as a list, but it's an Array
. This is because you didn't pattern-match on it at all: just tried to use your argument (an Array
) directly as a list.
Note that you'll still have to explicitly pattern-match on the result of drill
to tell whether it's a single element or a nested list. There's no way to make a type whose values can literally be either integers or nested lists in Haskell; Haskell's unions are tagged (i.e. the constructors are explicit), and it has no subtyping.
For more information, I suggest reading this introduction to algebraic data types from Learn You a Haskell.
Upvotes: 16