Are Foldable and Traversable replacement for Uniplate?

I have a kind of minimal language (sort of parser for CISCO-like CLI) that have parser described below. The parser should be serializable to JSON, that’s why not Parsec or Attoparsec.

I need a sort of completion tree for those commands, i.e for each prefix there are should be all possible sub-commands. Cp type describes basic command structure, i.e the whole language has type [Cp].

For building a completion tree I have to traverse the Cp type recursively and build all possible (Prefix, [Completion]) pairs.

I know how to do this manually. I know how to do this with uniplate (para should work). The question is: are Foldable/Traversable modern replacement for Uniplate, should I implement this using one of them?

For me it seems that types of Traversable doesn’t match my case. What about Foldable ? Should I use it or uniplate is still current and solution for cases like this?

type Str = Text

data Command = Command Prefix CmdArgs
               deriving Show

type Prefix  = [Str]
type CmdArgs = [CmdArg]
type CmdArg  = (Str,Str)

data Cp =  P Str              -- single token prefix
         | Arg Str            -- arbitrary string or atom
         | B Cp Cp            -- branch: first or second
         | S Cp Cp            -- non-empty sequence of items
         | O Cp               -- optional sequence
         | Discard Cp         -- discards result of nested parser
         | N                  -- null parser, parses nothing
         deriving (Generic,Show)


Having looked at your code I now doubt that either Foldable or Traversable will help.

As I mentioned in the comments, both are classes on type
constructors – i.e. types of kind * -> *, so you would
have to add a type parameter to data Cp, i.e.:

data Cp a =  P a
          |  Arg a
          |  B (Cp a) (Cp a)

But even if you did that, neither class quite fits your problem.

The methods in Travesable return another container of the same
type. (Presumably the returned container has the same shape.)

The methods in Foldable look more promising, but also won’t
work because the your folding function isn’t provided any
context as to where the a is coming from. That is, it won’t
be told if it is coming from a P constructor or an Arg

As mentioned in the docs for foldr, we have this “law”
for foldr:

foldr f z = foldr f z . toList

The foldr on the LHS is from the Foldable class whereas the foldr on the RHS is the one for lists. So a foldr on a Cp Str is equivalent
to a foldr on [Str] which clearly shows that you can’t treat a Str
which came from a P Str differently from one that came from an Arg Str.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *