Convert list to nested tuple Haskell

Question

Short and sweet, my issue is that I am parsing a list of numbers ([Integer]), and I want to transform that list into nested tuples, so for example the list [1,2,3,4] would be (1,(2,(3,4))) this seems to me to be doable with a fold operation. I think the problem I am having is that the type is not determined before hand, making the tuple nest potentially infinite.

EDIT BASED ON COMMENTS

Thanks for the good replies, the root problem is for an assignment, so that is why details of the greater issue is sparse, but in an effort to not leave you wondering I can expand a bit, although I am not looking for answers to the expansion. My problem boils down to an issue with a right recursive and right associative part of a context free grammar, where I have something like

A -> n A

so I could get an expression like so 'n n n n A' which parses to 'n(n(n(n A)))' (A does have other terminals). I can parse it to '[n,n,n,n] A', which is why I wanted the conversion (I know there is a better way, I am just struggling to find it).

You can't do this because the type depends on the data (full on dependent types). — Thomas M. DuBuisson
– Thomas M. DuBuisson, Commented Nov 2, 2019 at 22:01
Thanks for the answer, that was kinda the realization I was getting at, but was hoping I had overseen something. — dingo1337
– dingo1337, Commented Nov 2, 2019 at 22:09
You could define your own custom type data T = Empty | Nonempty (Integer, T) to represent the arbitrary nesting of tuples, but in doing that we are only giving another name to the standard list type, so there's nothing to gain. Why do you think you need tuples for your data? — chi
– chi, Commented Nov 2, 2019 at 22:21
Another possible encoding: data NTup t = Here t | There (NTup (Integer,t)). Then you can use NTup () for a nested tuple of any size. By the time you recurse down to Here, t will be a nested tuple of the appropriate size (try showing it to see). This is called a non-regular type, and I can't really see a point to doing it in this instance, but it's a good technique to know. — luqui
– luqui, Commented Nov 3, 2019 at 0:01

leftaroundabout · Accepted Answer · 2019-11-03 00:19:20Z

5

As Thomas M. DuBuisson commented, this is just not really doable in a good way, since the list length is only known at runtime, but tuples of different depth have different types, and types must be known at compile time.

(Technically speaking, Haskell is actually able to act as a full dynamically typed language, by using the Data.Dynamic type, but this really impractical to use.)

There is however another way to have a sensible-ish list-to-tuples conversion: if you do know at compile time what would be the correct depth, and a list of mismatching length should simply be an invalid input. In this case, you can use something like

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}

class NestedTup e t where
  toNestedTup :: [e] -> Maybe t

instance NestedTup e e where
  toNestedTup [e] = Just e
  toNestedTup _ = Nothing
instance NestedTup h t => NestedTup h (h,t) where
  toNestedTup (h:t) = (h,)<$>toNestedTup t
  toNestedTup [] = Nothing

*Main> toNestedTup [1,2,3,4 :: Int] :: Maybe (Int,(Int,(Int,Int)))
Just (1,(2,(3,4)))
*Main> toNestedTup [1,2,3,4,5 :: Int] :: Maybe (Int,(Int,(Int,Int)))
Nothing

answered Nov 3, 2019 at 0:19

leftaroundabout

121k6 gold badges185 silver badges337 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Yogendra Over a year ago

how did you add type constraints in instance definition, and how does it work? Also ghci complained about turning on TupleSections

luqui Over a year ago

@Yogendra you can do it just like that. instance <constraints> => ClassName params. It works by first selecting the instance as if there were no constraints, committing to that choice, and then trying to solve the constraints. (Thinking of it as an "if then", while tempting, seduces you into thinking you can do things you can't)

Collectives™ on Stack Overflow

Convert list to nested tuple Haskell

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related