how to compose a breadth-first search traversal with other concerns in Scala

Question

How to compose a simple breadth-first traversal of a graph with new concerns such as cache (to visited once each node) or distance.

with distance:

  def breadth_first_traverse2[Node](node: Node, f: Node => Seq[Node]): Stream[(Node, Int)] = {
    def recurse(q: Queue[(Node, Int)]): Stream[(Node, Int)] = {
      if (q.isEmpty) {
        Stream.Empty
      } else {
        val ((node, i), tail) = q.dequeue
        (node, i) #:: recurse(tail ++ f(node).map((_, i+1)))
      }
    }

    (node, 0) #:: recurse(Queue.empty ++ f(node).map((_, 1)))
  }

with cache :

  def breadth_first_traverse[Node](node: Node, f: Node => Seq[Node]): Stream[Node] = {
    def recurse(q: Queue[Node], cache: Set[Node]): Stream[Node] = {
      if (q.isEmpty) {
        Stream.Empty
      } else {
        val (node, tail) = q.dequeue
        val nodes = f(node).filterNot(cache.contains)
        node #:: recurse(tail ++ nodes, cache ++ nodes)
      }
    }

    node #:: recurse(Queue.empty ++ f(node), Set.empty)
  }

I've come up with those implementations. The problem is that new concerns are mixed with the simple implementation, so I can't compose things to have a new implementation with cache AND distance.

And if I also want to return the path from root to the node …

I'm wondering if FP patterns (like State or Traverse) could help here ?

Any idea for a cleaner design ?