How do I implement a recursive list in Haskell and methods to operate on it

Question

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?

That's not a list, that's a tree!

Daniel Wagner
– Daniel Wagner

2012-02-11 08:27:08 +00:00
Commented Feb 11, 2012 at 8:27 — Daniel Wagner
– Daniel Wagner, Commented Feb 11, 2012 at 8:27

ehird · Accepted Answer · 2012-02-11 03:15:46Z

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.

Collectives™ on Stack Overflow

How do I implement a recursive list in Haskell and methods to operate on it

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related