CODEWITHSUNDEEP
haskellrecursiontreebinary-tree
EightPinkArrows
EightPinkArrows

Reputation: 13

Haskell - Translate a list to a recursive data structure

I found this problem in a Haskell textbook. Given a recursive data structure:

data Foo = A Foo Foo | B Int Foo | C Int

create a function:

createFooFromList :: [Int] -> Foo -> Foo

that takes in a list and a Foo, applies the list to the Foo, and returns the new Foo.

What "applying" means is best described using an example.

Say we have a Foo that is defined as B 0 (B 1 (A (B 0 (C 1)) (B 1 (C 1)))) and we have to apply the list [0,0,1,0,2,0] to this Foo. To do this, simply take each integer in the given sequence and replace integers in the Foo structure in order with these integers in the sequence.

So for the above example, our output would be B 0 (B 0 (A (B 1 (C 0)) (B 2 (C 0))))

So far, I have created a function that applies the list to the B and C structures. C is trivial, and B is also easy as I simply set the head of the list to the Int parameter of B, and recursively apply the rest of the list to the Foo part of B. However I am unsure as to how to deal with A.

Upvotes: 1

Views: 215

Answers (1)

chi
chi

Reputation: 116139

Here is a hint:

I would start by writing an auxiliary function, which takes the [Int] and Foo arguments, and returns not just the output Foo but an additional [Int] representing the numbers in the input list which have not been used, yet. Hence, the resulting output type can be a pair.

The intuition here is that this auxiliary function does not assume that the input [Int] list contains the right amount of numbers for the Foo input, but allows more Ints to be present, and returns the ones in excess.

Using this auxiliary function, you can handle the A case with two Foos inside: you call the auxiliary function on the first Foo, and obtain the excess Ints, then you use those for the second Foo, and return the new excess Ints.

(A more advanced approach would be to use a State [Int] monad, but the above basic approach should be fine.)

Upvotes: 2

Related Questions