0

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)
  • Can you show what your uniplate code does? – ErikR Aug 5 '16 at 5:11
  • Actually, it seems that here acceptable "Evaluation" chapter from Uniplate manual, i.e. if I have to handle each case separately, uniplate is not applicable. Therefore, I have to write the recursing code manually or implement Foldable if I need to re-use this. But not idea, how to write Foldable/Traversable for this Cp type. – voidlizard Aug 5 '16 at 5:16
  • Well, both Foldable and Traversable apply to type constructors not concrete types. That is, Maybe is foldable, but not Maybe Int. So, at the very least you have to add a type parameter to Cp, e.g. data Cp a = .... If you show what goes on in your recursion I can give you a more complete answer. – ErikR Aug 5 '16 at 5:31
  • Control.Lens.Plated from lens is also an alternative to Uniplate, based on lensy traversals: hackage.haskell.org/package/lens-4.14/docs/… – Daniel Díaz Carrete Aug 5 '16 at 6:20
  • Here the approximate code: gist.github.com/voidlizard/… – voidlizard Aug 5 '16 at 6:30
1

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

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.