0

I've been writing my own version of Scala Cats (to assist others when learning this library). I've implemented my own versions of most type classes, but am stuck with a custom implementation of Traverse for State. The function to implement is:

def traverse[G[_]: Applicative, S, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]]

As a starter, I asked ChatGPT for an implementation in Scala Cats (since of course, it does not know my own library). A valid (simple) implementation in Cats should help me write a version in my own library. However, ChatGPT has failed me, with over-complicated solutions using the likes of StateT (of which currently I do not have an equivalent in my library). Also, the versions produced by ChatGPT do not compile.

One simple suggestion is the following, but does not compile:

import cats._
import cats.implicits._

def traverse[G[_]: Applicative, S, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]] = {
  val gb: G[B] =
    fa.runA _ andThen f

  val stateB: G[State[S, B]] =
    gb.map(b => State(s => (s, b)))

  stateB
}
Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
D Ainslie
  • 33
  • 1
  • 6

1 Answers1

4

Every Traversable (Traverse in Cats) is Foldable.

State is Applicative and Monad but not Foldable or Traversable

Why isn't the state monad traversable?

Are there non-trivial Foldable or Traversable instances that don't look like containers? (answer)

You can check that in Cats summoning Applicative[State[S, *]] and Monad[State[S, *]] compile but Foldable[State[S, *]] or Traverse[State[S, *]] doesn't.

State[S, A] is basically a function S => (S, A) (if we ignore wrapping, StateT, and Eval).

If State were a Foldable you'd be able to implement

def foldMap[S, A, B: Monoid](fa: S => (S, A))(f: A => B): B
// or
def foldLeft[S, A, B](fa: S => (S, A), b: B)(f: (B, A) => B): B

If State were a Traversable you'd be able to implement

def traverse[G[_]: Applicative, S, A, B](fa: S => (S, A))(f: A => G[B]): G[S => (S, B)]
// or
def sequence[G[_]: Applicative, A](fga: S => (S, G[A])): G[S => (S, A)]

Combining S => (S, A) and A => G[B] you can have S => (S, G[B]) but how to get G[S => (S, B)] if you only can do def ap[A, B](ff: G[A => B])(fa: G[A]): G[B] and def pure[A](x: A): G[A]?

Foldable means you can fold a structure into a value. Traversable means you can traverse a structure executing some applicative effect in every node of the structure. State is like a function, you can't fold it or traverse it.

Dmytro Mitin
  • 48,194
  • 3
  • 28
  • 66
  • Many thanks. A very nice explanation. It did not dawn on me, that I could not find a `State` instance for `Traverse` within the Cats library; but then again, even though it is a brilliant library, sometimes it takes a while to find in the source code, what one is looking for. – D Ainslie Mar 19 '23 at 11:25
  • What is interesting, is that when I failed to write a `State` instance for `Traverse`, at the time thinking it was possible, I asked ChatGPT, and not only did it respond "yes", it suggested a possible implementation (which as mentioned, did not compile). – D Ainslie Mar 19 '23 at 12:00
  • @DAinslie That's why ChatGPT is banned at SO https://meta.stackoverflow.com/questions/421831/temporary-policy-chatgpt-is-banned ChatGPT generates answers looking like human answers, not necessarily correct ones. – Dmytro Mitin Mar 19 '23 at 14:26
  • @DAinslie https://www.reddit.com/r/scala/comments/124ocqh/scala_and_chatgpt/ – Dmytro Mitin Apr 01 '23 at 12:10