1

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
EightPinkArrows
  • 13
  • 4
  • where is 2 in the output? – karakfa Nov 29 '19 at 16:10
  • Can you share what you have already done and where you are stuck? I would assume some kind of CPS approach, but this can be done in lots of ways. – Martin Kristiansen Nov 29 '19 at 16:26
  • 1
    What order? Breadth-first, depth-first, something else? – chepner Nov 29 '19 at 16:39
  • what if it's not possiblee "apply" the list? – is7s Nov 29 '19 at 16:40
  • @MartinKristiansen As I said in my question, I'm struggling with A. Right now my idea is that I would have some sort of secondary function that "scans" a certain path to find how many integers are in it, so that my algorithm can know how much of a list to supply to either Foo in A. – EightPinkArrows Nov 29 '19 at 16:49
  • This is very similar to the tree-labelling problem described in the documentation for [`Control.Monad.Trans.Lazy`](https://hackage.haskell.org/package/transformers-0.3.0.0/docs/Control-Monad-Trans-State-Lazy.html). – chepner Nov 29 '19 at 16:57
  • well, firstly, `B Int Foo == A (C Int) Foo` so the data type is needlessly overly complex. – Will Ness Nov 30 '19 at 07:28
  • @MartinKristiansen yes, [CPS works](https://stackoverflow.com/a/50588667/849891). it encodes state passing with [unique selection](https://stackoverflow.com/a/9889702/849891) from [shrinking domain](https://stackoverflow.com/search?q=user%3A849891+shrinking+domain). which is like parsing. – Will Ness Nov 30 '19 at 09:15
  • @chepner "Breadth-first, depth-first, something else?" not applicable. there's no data in nodes, only in leaves. the intent is fringe replacement. – Will Ness Nov 30 '19 at 09:24

1 Answers1

2

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.)

chi
  • 111,837
  • 3
  • 133
  • 218