CODEWITHSUNDEEP
haskellgeneric-programminguniplate
alias
alias

Reputation: 30450

Can uniplate's `universeBi` be used to retrieve nodes in a breadth-first fashion?

Is it possible to use Uniplate's universeBi to get the output in breadth-first-order? It appears the results are returned in a depth-first fashion. I'm wondering how I can use uniplate to retrieve the universeBi in a breadth-first fashion.

To illustrate, consider the following toy program:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Data
import Data.Generics.Uniplate.Data

data A = A B Int deriving (Data, Typeable)
data B = B Int   deriving (Data, Typeable)

val :: A
val = A (B 1) 2

ints :: [Int]
ints = universeBi val

I get:

*Main> ints
[1,2]

But this is depth-first, as 1 is obtained from the B node. I'd rather get it in the breadth-first order, i.e., receive [2,1]. Is this achievable in uniplate?

Upvotes: 1

Views: 127

Answers (1)

HTNW
HTNW

Reputation: 29193

You can dig into the structure of the Str returned by biplate:

layers :: Str a -> [[a]]
layers Zero = []
layers (One x) = [[x]]
layers (Two f x) = catLayers (layers f) ([] : layers x)
  where catLayers [] ys = ys
        catLayers xs [] = xs
        catLayers (x : xs) (y : ys) = (x ++ y) : catLayers xs ys
layersBi :: Biplate from to => from -> [[to]]
layersBi = layers . fst . biplate
breadthBi :: Biplate from to => from -> [to]
breadthBi = concat . layersBi

So now

breadthBi (A (B 1) 2) :: [Int]
-- = [2, 1]

and

data Tree a = Branch (Tree a) a (Tree a) | Leaf deriving (Data, Typeable)
--       4
--   2       6
-- 1   3   5   7
example = Branch (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) 4 (Branch (Branch Leaf 5 Leaf) 6 (Branch Leaf 7 Leaf))
(layersBi :: Data a => Tree a -> [[a]]) example
-- = [[],[4],[2,6],[1,3,5,7]]

I'm not sure if it's actually guaranteed that Str exactly reflects the structure of the data type, but it appears to. You could instead cook something out of the Data primitives if you have to.

Upvotes: 1

Related Questions