CODEWITHSUNDEEP
haskell
user65526
user65526

Reputation: 705

Flattening tuples in Haskell

In Haskell we can flatten a list of lists Flatten a list of lists

For simple cases of tuples, I can see how we would flatten certain tuples, as in the following examples:

flatten :: (a, (b, c)) -> (a, b, c)
flatten x = (fst x, fst(snd x), snd(snd x))

flatten2 :: ((a, b), c) -> (a, b, c)
flatten2 x = (fst(fst x), snd(fst x), snd x)

However, I'm after a function that accepts as input any nested tuple and which flattens that tuple.

Can such a function be created in Haskell?

If one cannot be created, why is this the case?

Upvotes: 4

Views: 1238

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153352

No, it's not really possible. There are two hurdles to clear.

The first is that all the different sizes of tuples are different type constructors. (,) and (,,) are not really related to each other at all, except in that they happen to be spelled with a similar sequence of characters. Since there are infinitely many such constructors in Haskell, having a function which did something interesting for all of them would require a typeclass with infinitely many instances. Whoops!

The second is that there are some very natural expectations we naively have about such a function, and these expectations conflict with each other. Suppose we managed to create such a function, named flatten. Any one of the following chunks of code seems very natural at first glance, if taken in isolation:

flattenA :: ((Int, Bool), Char) -> (Int, Bool, Char)
flattenA = flatten

flattenB :: ((a, b), c) -> (a, b, c)
flattenB = flatten

flattenC :: ((Int, Bool), (Char, String)) -> (Int, Bool, Char, String)
flattenC = flatten

But taken together, they seem a bit problematic: flattenB = flatten can't possibly be type-correct if both flattenA and flattenC are! Both of the input types for flattenA and flattenC unify with the input type to flattenB -- they are both pairs whose first component is itself a pair -- but flattenA and flattenC return outputs with differing numbers of components. In short, the core problem is that when we write (a, b), we don't yet know whether a or b is itself a tuple and should be "recursively" flattened.

With sufficient effort, it is possible to do enough type-level programming to put together something that sometimes works on limited-size tuples. But it is 1. a lot of up-front effort, 2. very little long-term programming efficiency payoff, and 3. even at use sites requires a fair amount of boilerplate. That's a bad combo; if there's use-site boilerplate, then you might as well just write the function you cared about in the first place, since it's generally so short to do so anyway.

Upvotes: 12

Related Questions