Example of generic free algebra with Cats and Freestyle. Additional type args beyond F[_] in algebras are not currently supported. To work around we use path dependent types.

GenericFreeAlgebra.scala

import cats.data.State
import freestyle.free._

/* domain objects */
sealed trait Acme
object Acme {
  case object AcmeUK extends Acme
  case object AcmeUS extends Acme
}

case class CommonId(id: String)
trait Item[A <: Acme] {
  val id: CommonId
}

case class AcmeUKItem(id: CommonId) extends Item[Acme.AcmeUK.type]
case class AcmeUSItem(id: CommonId) extends Item[Acme.AcmeUS.type]

/* state */
trait MapState[K, V] {
  type Type     = Map[K, V]
  type TypeA[A] = State[Type, A]

  def apply(state: Map[K, V]): Type = state
  def apply(state: (K, V)*): Type   = state.toMap
  def empty: Type                   = Map.empty[K, V]
}

trait CommonState[A <: Acme] extends MapState[CommonId, Item[A]]
object AcmeUKState           extends CommonState[Acme.AcmeUK.type]
object AcmeUSState           extends CommonState[Acme.AcmeUS.type]

/* freestyle free */
trait AcmeStorage[A <: Acme] {
  @free trait Algebra {
    def put(item: Item[A]): FS[Unit]
    def get(id: CommonId): FS[Option[Item[A]]]
  }
}

object GenericFreeAcme extends App {
  object AcmeUKStorage extends AcmeStorage[Acme.AcmeUK.type]

  implicit val acmeUKStorageHandler = new AcmeUKStorage.Algebra.Handler[AcmeUKState.TypeA] {
    def put(item: Item[Acme.AcmeUK.type]): AcmeUKState.TypeA[Unit]           = State.modify(_.updated(item.id, item))
    def get(id: CommonId): AcmeUKState.TypeA[Option[Item[Acme.AcmeUK.type]]] = State.inspect(_.get(id))
  }

  val ukOps      = AcmeUKStorage.Algebra.to[AcmeUKStorage.Algebra.Op]
  val inputState = AcmeUKState.empty

  val (id1, id2, id3)             = (CommonId("foo"), CommonId("bar"), CommonId("baz"))
  val (ukItem1, ukItem2, ukItem3) = (AcmeUKItem(id1), AcmeUKItem(id2), AcmeUKItem(id3))

  val program = for {
    _   <- ukOps.put(ukItem1)
    _   <- ukOps.put(ukItem2)
    _   <- ukOps.put(ukItem3)
    mid <- ukOps.get(id2)
  } yield mid

  val (outputState, result) = program.interpret[AcmeUKState.TypeA].run(inputState).value

  val assertion1 = outputState == AcmeUKState(id1 -> ukItem1, id2 -> ukItem2, id3 -> ukItem3)
  val assertion2 = result == Some(ukItem2)
  println("%s << outputState == AcmeUKState(id1 -> ukItem1, id2 -> ukItem2, id3 -> ukItem3)".format(assertion1))
  // true << outputState == AcmeUKState(id1 -> ukItem1, id2 -> ukItem2, id3 -> ukItem3)
  // true << result == Some(ukItem2)
}