some sort of monad defined in terms of a sort of fold

thing.scala

package thing

import scala.language.higherKinds

trait Thing[+T, Context[_]] { parent =>
  def foldish[S](s0: S)(f: (S, T) => Context[S]): Context[S]

  def map[U](g: T => U) = new Thing[U, Context] {
    def foldish[S](s0: S)(f: (S, U) => Context[S]) =
      parent.foldish(s0)((s, t) => f(s, g(t)))
  }

  def flatMap[U](g: T => Thing[U, Context]) = new Thing[U, Context] {
    def foldish[S](s0: S)(f: (S, U) => Context[S]) =
      parent.foldish(s0)((s, t) => g(t).foldish(s)(f))
  }
}

object Thing {
  def constant[T, Context[_]](t: T) = new Thing[T, Context] {
    def foldish[S](s0: S)(f: (S, T) => Context[S]): Context[S] = f(s0, t)
  }

  def empty[Context[_]]: Thing[Nothing, Context] = ??? // can't define an empty Thing, unlike scalaz.Foldable
  def emptyOfT[T, Context[_]]: Thing[T, Context] = empty // it is covariant anyway
}