FreekTest.scala

object FreekQuickSearch {

  import cats.free.Free
  import cats.data.Xor
  import freek._

  final case class Wrong(message: String, cause: Option[Throwable] = None)
  type Maybe[A] = Xor[Wrong, A]

  ///
  /// Domain: a parser, a log, a backend processing query
  ///

  final case class Result(value: String)

  // log
  sealed trait Log[A]
  object Log {
    final case class DebugMsg(msg: String) extends Log[Unit]
  }

  /// parser
  sealed trait Parser[A]
  object Parser {
    final case class Parse(input: String) extends Parser[Maybe[Query]]
  }

  /// backend processing
  sealed trait Backend[A]
  object Backend {
    final case class Search(query: Query) extends Backend[Maybe[Seq[Result]]]
  }

  type PRG = Parser :|: Log :|: Backend :|: FXNil
  val PRG = Program[PRG]
  type O = Maybe :&: Bulb


  /// parse user input, log query, process query
  def search(input: String) = {
    for {
      query   <- Parser.Parse(input).freeko[PRG, O]     // error 1
      _       <- Log.DebugMsg(s"User query for '${input}', parsed as user query: '${query.userToken}' on objects: " +
                              s"'${query.objectClass.mkString(", ")}' and attributes '${query.attributes.mkString(", ")}'"
                 ).freeko[PRG, O]
      results <- Backend.Search(query).freeko[PRG, O]  // error 2
    } yield {
      results
    }
  }
}

/*
1:
type mismatch;  found   : 
  com.normation.rudder.services.quicksearch.Query => freek.OnionT[cats.free.Free,[t(in type Cop)]freek.
  In3[com.normation.rudder.services.quicksearch.FreekQuickSearch.Parser,com.normation.
  rudder.services.quicksearch.FreekQuickSearch.Log,com.normation.rudder.services.quicksearch.FreekQuickSearch.
  Backend,t(in type Cop)],freek.:&:[[A]cats.data.Xor[com.normation.rudder.services.quicksearch.FreekQuickSearch.
  Wrong,A],freek.Bulb], 
  Nothing]  
required: 
  com.normation.rudder.services.quicksearch.Query => freek.OnionT[cats.free.Free,[t(in type Cop)]freek.
  In3[com.normation.rudder.services.quicksearch.FreekQuickSearch.Parser,com.normation.
  rudder.services.quicksearch.FreekQuickSearch.Log,com.normation.rudder.services.quicksearch.FreekQuickSearch.
  Backend,t(in type Cop)],freek.:&:[[A]cats.data.Xor[com.normation.rudder.services.quicksearch.FreekQuickSearch.
  Wrong,A],freek.Bulb],
  B]	
  

2:
could not find implicit value for parameter lifter2: 
  freek.Lifter2.Aux[com.normation.rudder.services.quicksearch.FreekQuickSearch.Maybe[Seq[com.normation.rudder.services.
  quicksearch.FreekQuickSearch.Result]],com.normation.rudder.services.quicksearch.FreekQuickSearch.O,A]
not enough arguments for method freeko: (implicit ga: freek.HKK.Aux[com.normation.rudder.services.quicksearch.
  FreekQuickSearch.Maybe[Seq[com.normation.rudder.services.quicksearch.FreekQuickSearch.Result]],com.normation.rudder.
  services.quicksearch.FreekQuickSearch.Result], implicit subfx: freek.SubFX[[β]freek.In1[com.normation.rudder.services.
  quicksearch.FreekQuickSearch.Backend,β],com.normation.rudder.services.quicksearch.
  FreekQuickSearch.PRG], implicit lifter2: freek.Lifter2.Aux[com.normation.rudder.services.quicksearch.FreekQuickSearch.
  Maybe[Seq[com.normation.rudder.services.quicksearch.FreekQuickSearch.Result]],com.normation.rudder.services.quicksearch.
  FreekQuickSearch.O,com.normation.rudder.services.quicksearch.FreekQuickSearch.Result], implicit pointer: freek.
  Pointer[com.normation.rudder.services.quicksearch.FreekQuickSearch.O], implicit mapper: freek.Mapper[com.normation.rudder.
  services.quicksearch.FreekQuickSearch.O], implicit binder: freek.Binder[com.normation.rudder.services.quicksearch.
  FreekQuickSearch.O], implicit traverser: freek.Traverser[com.normation.rudder.services.quicksearch.FreekQuickSearch.O])freek.
  OnionT[cats.free.Free,subfx.Cop,com.normation.rudder.services.quicksearch.FreekQuickSearch.O,com.normation.rudder.services.
  quicksearch.FreekQuickSearch.Result]. Unspecified value parameters lifter2, pointer, mapper...
*/

object FreekQuickSearch {

      // import cats.free.Free
      // import cats.data.Xor
      // import freek._

      case class Query(userToken: String, objectClass: List[String], attributes: List[String])

      final case class Wrong(message: String, cause: Option[Throwable] = None)
      type Maybe[A] = Xor[Wrong, A]

      ///
      /// Domain: a parser, a log, a backend processing query
      ///

      final case class Result(value: String)

      // log
      sealed trait Log[A]
      object Log {
        final case class DebugMsg(msg: String) extends Log[Unit]
      }

      /// parser
      sealed trait Parser[A]
      object Parser {
        final case class Parse(input: String) extends Parser[Maybe[Query]]
      }

      /// backend processing
      sealed trait Backend[A]
      object Backend {
        final case class Search(query: Query) extends Backend[Maybe[List[Result]]]
      }

      type PRG = Parser :|: Log :|: Backend :|: FXNil
      val PRG = Program[PRG]
      type O = Maybe :&: List :&: Bulb

      /// parse user input, log query, process query
      def search(input: String) = {
        for {
          query   <- Parser.Parse(input).freeko[PRG, O]     // error 1
          _       <- Log.DebugMsg(s"User query for '${input}', parsed as user query: '${query.userToken}' on objects: " +
                                  s"'${query.objectClass.mkString(", ")}' and attributes '${query.attributes.mkString(", ")}'"
                     ).freeko[PRG, O]
          // here you can't use freeko due to limitations of implicits conversion...
          // once an implicit convention has been chosen, it doesn't backdrack...
          // I've chosen (by convention) to make freeko take by default the deeper stack to resolve the onion O in freeko...
          // In your case, it searches `Maybe :&: Seq` in the Onion and fails as expected but doesn't try other solutions...
          // For this case, I have this onionP function that stops at first layer...
          // Maybe we could do better but haven't found solution yet...
          results <- Backend.Search(query).freeko[PRG, O]  // error 2
        } yield {
          results
        }
      }
    }
    FreekQuickSearch.search("toto")

  }

object FreekQuickSearch {

      // import cats.free.Free
      // import cats.data.Xor
      // import freek._

      case class Query(userToken: String, objectClass: List[String], attributes: List[String])

      final case class Wrong(message: String, cause: Option[Throwable] = None)
      type Maybe[A] = Xor[Wrong, A]

      ///
      /// Domain: a parser, a log, a backend processing query
      ///

      final case class Result(value: String)

      // log
      sealed trait Log[A]
      object Log {
        final case class DebugMsg(msg: String) extends Log[Unit]
      }

      /// parser
      sealed trait Parser[A]
      object Parser {
        final case class Parse(input: String) extends Parser[Maybe[Query]]
      }

      /// backend processing
      sealed trait Backend[A]
      object Backend {
        final case class Search(query: Query) extends Backend[Maybe[List[Result]]]
      }

      type PRG = Parser :|: Log :|: Backend :|: FXNil
      val PRG = Program[PRG]
      type O = Maybe :&: List :&: Bulb

      /// parse user input, log query, process query
      def search(input: String) = {
        for {
          lquery   <- Parser.Parse(input).freeko[PRG, O].peelRight   // error 1
          List(query) = lquery
          _       <- Log.DebugMsg(s"User query for '${input}', parsed as user query: '${query.userToken}' on objects: " +
                                  s"'${query.objectClass.mkString(", ")}' and attributes '${query.attributes.mkString(", ")}'"
                     ).freeko[PRG, O].peelRight
          // here you can't use freeko due to limitations of implicits conversion...
          // once an implicit convention has been chosen, it doesn't backdrack...
          // I've chosen (by convention) to make freeko take by default the deeper stack to resolve the onion O in freeko...
          // In your case, it searches `Maybe :&: Seq` in the Onion and fails as expected but doesn't try other solutions...
          // For this case, I have this onionP function that stops at first layer...
          // Maybe we could do better but haven't found solution yet...
          results <- Backend.Search(query).freeko[PRG, O].peelRight  // error 2
        } yield {
          results
        }
      }
    }
    FreekQuickSearch.search("toto")

  }

@mandubian
The last one seems to be the only one giving a Vector[Result] - which is the expected type.
The other two are returning a Xor[..., Vector[Result]], certainly because they only go one frame deep in the stack (but we would like them to go two frames deep, or perhaps "keep only the last K frames". You don't have something like that in Freek, it seems I always need it :/