CODEWITHSUNDEEP
haskelltuples
Aistis Raulinaitis
Aistis Raulinaitis

Reputation: 85

A list of list or a tuple of tuples

I was just wondering if there is a possibility to create a function that returns an (hopefully infinite) list of numbers similar to this. [1, [2, [3, [4]]]].

The closest I got was this.

func list 0 = list
func list num = func newList (num-1) 
                where newList = list ++ [[num]]

This is used something like this.

func [] 3

Which returns this.

[[3],[2],[1]]

Now I know that this is not infinite nor is it in the correct order but I just wanted to show that I was at least attempting something before posting. :)

Thanks a bunch!

Upvotes: 3

Views: 290

Answers (3)

Ben Millwood
Ben Millwood

Reputation: 7001

The key is to come up with the correct type.

If you want something like [1, [2, [3, [4]]]], then doing exactly that won't work, because all list elements must be the same type.

This makes sense, because when I grab an element out of the list, I need to know what type it is before I can do anything with it (this is sort of the whole point of types, they tell you what you can and can't do with a thing).

But since Haskell's type system is static, I need to know what type it is even without knowing which element of the list it is, because which list index I'm grabbing might not be known until the program runs. So I pretty much have to get the same type of thing whatever index I use.

However, it's possible to do something very much like what you want: you want a data type that might be an integer, or might be a list:

type IntegerOrList a = Either Integer [a]

If you're not familiar with the Either type, a value of Either l r can either be Left x for some x :: l, or Right y for some y :: r. So IntegerOrList a is a type whose values are either an integer or a list of something. So we can make a list of those things: the following is a value of type [IntegerOrList Bool]:

[Left 7, Left 4, Right [True, False], Left 8, Right [], Right [False]]

Okay, so that's one level of lists inside lists, but we can't put lists inside lists inside lists yet – the inner lists contain Bools, which can't be lists. If we instead had [IntegerOrList (IntegerOrList Bool)], we'd be able to have lists inside lists inside lists, but we'd still get no further. In our example, we had a list which contained values which were either integers or lists, and the lists were lists which contained values which were either integers or lists, and... what we really want is something like IntegerOrList (IntegerOrList (IntegerOrList ..., or more simply, something like:

type IntegerOrLists = Either Integer [IntegerOrLists]

But that's not allowed – type synonyms can't be recursive, because that would produce an infinitely large type, which is confusing for the poor compiler. However, proper data types can be recursive:

data IntegerOrLists = I Integer | L [IntegerOrLists]

Now you can build lists like these, mixing integers and lists of your type:

L [I 1, L [I 2, L [I 3, L [I 4]]]]

The key is that whether each item is an integer or a list has to be flagged by using the I or L constructors. Now each element of the list is of type IntegerOrLists, and we can distinguish which it is by looking at that constructor. So the typechecker is happy at last.

Upvotes: 2

Landei
Landei

Reputation: 54584

{-# LANGUAGE ExistentialQuantification #-}

class Foo a

instance Foo Int
instance Foo [a]

data F = forall a. Foo a => F a

test = F [F (1 :: Int), F [F (2 :: Int), F [F (3 :: Int), F [F (4 :: Int)]]]]

This example shows

  • That you can have such structures in Haskell, just use some gift wrapping
  • That these structures are practically useless (try to do something with it)

Upvotes: 1

Federico Squartini
Federico Squartini

Reputation: 1218

You cannot write such a function, because all elements of a list must have the same type. The list you want to create would not typecheck even in the case of just two elements:

Prelude> :t [1::Int,[2::Int]]

<interactive>:1:9:
    Couldn't match expected type `Int' with actual type `[Int]'
    In the expression: [2 :: Int]
    In the expression: [1 :: Int, [2 :: Int]]

First element is a Int, second one a list of Int, hence typechecking fails.

Although you can express the result with tuples, e.g.

Prelude> :t (1::Int,(2::Int,(3::Int,4::Int)))
(1::Int,(2::Int,(3::Int,4::Int))) :: (Int, (Int, (Int, Int)))

You still cannot write the function, because the type of the result would change depending on the number of elements you wish to have. Let's call f the hypothetical function:

f 1 :: (Int)
f 2 :: (Int,(Int))
f 3 :: (Int,(Int,(Int)))
...

The type of f changes with the argument, so f cannot be written.

Upvotes: 8

Related Questions