traverse and state monad causing stackoverflow

855 views
Skip to first unread message

huynhjl

unread,
Oct 9, 2011, 3:32:58 AM10/9/11
to scalaz
I keep running into those stack overflows. I was about to post a
question on whether there is a way to not traverse the entire vector,
and wanted to verify that my assumption that it would traverse the
whole vector was correct.

import scalaz._
import Scalaz._

type StS[x] = State[(Set[Int], Boolean), x]

def hasDups(v: Vector[Int]): Boolean = {
val (_, result) = v.traverse[StS, Unit]{ i => state{ case (set,
result) =>
if (result || (set contains i)) {
(set, true) -> ()
} else {
(set + i, false) -> ()
}
}
} ~> (Set[Int](), false)
result
}

hasDups(Vector.range(0, 10000))

And I get:
java.lang.StackOverflowError
[..snip..]
at scalaz.MAsLow$$anon$2.$u2218(MAB.scala:50)
at scalaz.TraverseLow$$anon$20$$anonfun$5.apply(Traverse.scala:147)
at scalaz.TraverseLow$$anon$20$$anonfun$5.apply(Traverse.scala:147)
at scalaz.Foldable$$anon$13.foldRight(Foldable.scala:95)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)
at scalaz.TraverseLow$$anon$20$$anonfun$5.apply(Traverse.scala:147)
at scalaz.TraverseLow$$anon$20$$anonfun$5.apply(Traverse.scala:147)
at scalaz.Foldable$$anon$13.foldRight(Foldable.scala:95)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)

Are those known limitations? I see foldRight. I sort of recall from
reading something somewhere years ago that foldRight aren't tail
recursive. How should I approach this problem? And back to my original
question is there a way to stop traversing if my state satisfies a
particular predicate?

-- Jean-Laurent

Runar Bjarnason

unread,
Oct 14, 2011, 2:40:04 PM10/14/11
to sca...@googlegroups.com
Try this very small change in the type signature of hasDups:

def hasDups[F[_]:Traverse](v: F[Int]): Boolean



--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.


huynhjl

unread,
Oct 14, 2011, 9:02:12 PM10/14/11
to scalaz
I just tried that but it doesn't make any difference that I can see.
Still overflows.

Yo Eight

unread,
Oct 22, 2011, 11:59:41 AM10/22/11
to scalaz
I got the same error except I'm using traverse from Stream to IO

Runar Oli

unread,
Oct 22, 2011, 12:18:41 PM10/22/11
to sca...@googlegroups.com
IO has changed since last release. See if pulling the latest snapshot build fixes your SOE problem.

Yo Eight

unread,
Oct 22, 2011, 2:42:41 PM10/22/11
to scalaz
I've moved to 6.0.4-SNAPSHOT and I still have SOE.

I don't think IO is involved, here my stacktrace snippet:

at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634)
at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626)
at scala.collection.immutable.Stream$$anonfun$append
$1.apply(Stream.scala:80)
at scala.collection.immutable.Stream$$anonfun$append
$1.apply(Stream.scala:80)
at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634)
at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626)
at scala.collection.immutable.Stream$$anonfun$append
$1.apply(Stream.scala:80)
at scala.collection.immutable.Stream$$anonfun$append
$1.apply(Stream.scala:80)
at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634)
at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Foldable$$anon$13.foldRight(Foldable.scala:95)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Foldable$$anon$13.foldRight(Foldable.scala:95)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)
at scalaz.Foldable$$anon$13.foldRight(Foldable.scala:95)
at scalaz.Foldable$$anon$13$$anonfun$foldRight$6.apply(Foldable.scala:
95)
at scalaz.Traverse$$anon$4$$anonfun$traverse$6.apply(Traverse.scala:
31)

Since Foldable[Stream].foldRight isn't tail recursive that might be
a problem when dealing with 'big' streams (those of mine have 10k
elements). For me this isn't a blocking issue since I've got several
workarounds (but traverse seems to be more elegant)


On Oct 22, 6:18 pm, Runar Oli <runaror...@gmail.com> wrote:
> IO has changed since last release. See if pulling the latest snapshot build fixes your SOE problem.
>

Yo Eight

unread,
Oct 22, 2011, 8:12:35 PM10/22/11
to scalaz
Here is a simple code to reproduce the SOE:

val MAX = 10000
def bigStream(i: Int): Stream[Int] = {
if(i > MAX) Stream.empty
else i #:: (bigStream(i + 1))
}

bigStream(1).traverse(x => putStrLn(x.toString)).unsafePerformIO

Derek Williams

unread,
Oct 22, 2011, 10:29:36 PM10/22/11
to sca...@googlegroups.com
On Sat, Oct 22, 2011 at 12:42 PM, Yo Eight <yo.e...@gmail.com> wrote:
 Since Foldable[Stream].foldRight isn't tail recursive that might be
a problem when dealing with 'big' streams (those of mine have 10k
elements). For me this isn't a blocking issue since I've got several
workarounds (but traverse seems to be more elegant)


If you put something like this Traverse implementation in scope it should fix your problems:

  implicit def TraversableTraverse[CC[X] <: collection.SeqLike[X, CC[X]] : CanBuildAnySelf] = new Traverse[CC] {
    def traverse[F[_]: Applicative, A, B](f: A => F[B], as: CC[A]): F[CC[B]] = {
      val cbf = implicitly[CanBuildAnySelf[CC]].builder[B, B]
      (Vector.empty[B].pure[F] /: as)((bs, a) => (bs <**> f(a))(_ :+ _)) map (v => (cbf.apply() ++= v).result)
    }
  }

--
Derek Williams

huynhjl

unread,
Oct 22, 2011, 11:07:55 PM10/22/11
to scalaz
Going all the way back on my Oct 9th message where I wondered about
foldRight.

I really think now this has to do with fold right.

Those examples will blow the stack:

Stream.from(1).take(10000).traverse(some(_))
Vector(1 to 10000: _*).traverse(some(_))

This is due to the use of foldr for those cases:
https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Traverse.scala#L31
https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Traverse.scala#L147

foldr is not tail recursive:
https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Foldable.scala#L95

Stream.from(1).take(10000).foldr(1)((_, acc) => acc)
(also stack overflows)

Note that List does not have this issue as it use foldLeft (at least
on master).

I'm not sure how this is implemented in haskell and how ghc optimizes
this situation, but scala and the JVM certainly cannot handle this.

(or course I may be completely mistaken in which case I'm glad if
somebody can correct me)

--Jean-Laurent

huynhjl

unread,
Oct 23, 2011, 7:01:02 AM10/23/11
to scalaz
Cool. Testing with scalaz-core_2.9.1-6.0.4-SNAPSHOT.jar, it fixes Yo
Eight's test case.

My state example also goes a bit further. Now I hit a different stack
overflow issue:

Stream.from(1).take(10000).traverse[({type S[x]=State[Int,x]})#S,
String]{ i =>
state[Int,String](s => (s + 1, i + "!"))
} apply 0

java.lang.StackOverflowError
at scalaz.State$$anonfun$map$1.<init>(State.scala:8)
at scalaz.State$class.map(State.scala:8)
at scalaz.States$$anon$1.map(State.scala:44)
at scalaz.Functor$$anon$1.fmap(Functor.scala:43)
at scalaz.Functor$$anon$1.fmap(Functor.scala:42)
at scalaz.Applys$$anon$2$$anonfun$apply$1.apply(Apply.scala:
12)
at scalaz.Applys$$anon$2$$anonfun$apply$1.apply(Apply.scala:
12)
at scalaz.State$$anonfun$flatMap$1.apply(State.scala:13)
at scalaz.State$$anonfun$flatMap$1.apply(State.scala:12)
at scalaz.States$$anon$1.apply(State.scala:45)
at scalaz.State$$anonfun$flatMap$1.apply(State.scala:12)

On Oct 22, 7:29 pm, Derek Williams <de...@fyrie.net> wrote:

Yo Eight

unread,
Oct 23, 2011, 8:24:56 AM10/23/11
to scalaz
I was unable to make it work on 6.0.4-SNAPSHOT (2.9.1) independently
of the Applicative instance I'm using to traverse my Stream[Int]
( first Applicative[IO] then Applicative[State])

huynhjl

unread,
Oct 23, 2011, 8:32:11 AM10/23/11
to scalaz
What is the repeated cycle of the stack trace? Is it in State or
Traverse/Foldable or something else?

Yo Eight

unread,
Oct 23, 2011, 8:42:11 AM10/23/11
to scalaz
Traverse/Foldable

etorreborre

unread,
Dec 2, 2011, 2:33:15 AM12/2/11
to sca...@googlegroups.com
I just had the same issue and created a ticket on Github because I don't know if any of you found the solution

It seems to me that the real problem is not so much that the fold is left or right, but more that we're folding anyway! That is, we reduce the full structure to something even if that something is another Stream. 

In this article, it says "traverse with Maybe is strict, so doesn’t work on stream", but I'm not sure how this apply to our case and how to work around it.

If I found anything I'll come back to you :-).

Eric.

etorreborre

unread,
Dec 2, 2011, 2:44:00 AM12/2/11
to sca...@googlegroups.com
I also suspect that the solution is described here.

But I don't know yet exactly how to use it :-(.

Yo Eight

unread,
Dec 2, 2011, 7:44:06 AM12/2/11
to scalaz
Trampoline trick aims to avoid SOE when chaining a lot of flatMap
calls. You will have SOE when traversing your Stream because
Traversable[Stream] uses foldRight, which is not tail recursive

Traversing a big strict list won't get you a SOE if you are using the
last snapshot.

Traversing a 'huge' lazy list causes a SOE on Haskell too

On Dec 2, 8:44 am, etorreborre <etorrebo...@gmail.com> wrote:
> I also suspect that the solution is described here<http://apocalisp.wordpress.com/2011/10/26/tail-call-elimination-in-sc...>

Matthew Pocock

unread,
Dec 2, 2011, 9:52:51 AM12/2/11
to sca...@googlegroups.com
Just thinking out loud, but shouldn't it be possible to implement a foldRight as a foldLeft that accumulates a huge thunk (lots of f o f)  and then evaluates it when the zero is hit? It shifts the stack into the heap.

Matthew

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.




--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle University
skype: matthew.pocock
tel: (0191) 2566550

Runar Bjarnason

unread,
Dec 2, 2011, 10:19:26 AM12/2/11
to sca...@googlegroups.com
Yeah, this is how Foldable[List].foldr is implemented.

Runar Bjarnason

unread,
Dec 2, 2011, 4:57:07 PM12/2/11
to sca...@googlegroups.com
scala> val counter = stateT((i:Int) => suspend((i+1, i+1)))
counter: scalaz.StateT[scalaz.Coroutine.Trampoline,Int,Int] = scalaz.States$$anon$2@16b19f8a

scala> implicit val tm: Monad[Trampoline] = Monad.monad(trampolineBind, trampolinePure)
tm: scalaz.Monad[scalaz.Coroutine.Trampoline] = scalaz.MonadLow$$anon$1@3b9ed9ee

scala> implicit def m[A] = Monad.StateTMonad[Trampoline, A](trampolineBind, trampolinePure)
m: [A]=> scalaz.Monad[[x]scalaz.StateT[scalaz.Coroutine.Trampoline,A,x]]

scala> val traversed: StateT[Trampoline, Int, List[Int]] = (Stream.from(5)).take(10000).toList.traverse[({type l[a]=StateT[Trampoline, Int, a]})#l, Int](i => counter)
traversed: scalaz.StateT[scalaz.Coroutine.Trampoline,Int,List[Int]] = scalaz.States$$anon$2@7a27f5ad

scala> traversed ! 5
res12: scalaz.Coroutine.Trampoline[List[Int]] = Gosub(Suspend(<function0>),<function1>)

scala> res12.run
res13: List[Int] = List(6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177,
178, 179, 1...


This only works because Foldable[List].foldr is implemented as a left fold.

etorreborre

unread,
Dec 2, 2011, 6:55:00 PM12/2/11
to sca...@googlegroups.com
Thanks Runar, that's some progress indeed!

However my use case is to start from a stream (I'm reading from a file, I can't hold everything in memory) and I want to traverse it with a StateT[M, S, A] where:

 - M is any kind of effect, but it is actually a mix of IO to display messages and store things in a database
 - S is some state I'm keeping to notify the user when we've read 100 lines, 1000, 10.000 and so on

Let's we forget the fact that I would like to traverse a Stream with a StateT instead of a State (which complexifies a bit the type signatures), and just focus on the Stream traversal. I've tried to implement a Traverse instance for streams where we use foldLeft instead of foldRight. When I run the code:

    val traversed = ma(Stream.from(5)).traverse[({type l[a]=StateT[Trampoline, Int, a]})#l, Int](i => counter)
    val started = traversed ! 5
    val result: Stream[Int] = started.run
    result.take(3) must_== List(6, 7, 8)

I don't get an SOE anymore but it doesn't terminate either! I think that the reason is that, during the traversal, we fold the whole stream first (which never ends,...) before returning it. Yesterday, I tried to implement traverse differently for Stream to avoid that but I wasn't successful.

Am I right in my analysis? What would be the good way to implement traverse for streams then?

Thanks again,

Eric

Runar Oli

unread,
Dec 2, 2011, 7:01:23 PM12/2/11
to sca...@googlegroups.com, sca...@googlegroups.com
Try StreamT
--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To view this discussion on the web visit https://groups.google.com/d/msg/scalaz/-/Srypc61Agg0J.

Paul Chiusano

unread,
Dec 4, 2011, 3:10:31 PM12/4/11
to sca...@googlegroups.com
To elaborate a bit - traversing streams with state actions can't in general be don't in constant space. To see why, suppose we want to convert a Stream[State[Int,A]] to a State[Int, Stream[A]]. And say we have:

val x: Stream[Int => (A,Int)]
val y: Int => (Stream[A],Int) = x.sequence

When calling this function y: Int => (Stream[A],Int), we are going to have to traverse the entire Stream x. To see this, think about if all the state actions were modify(1 + _). Clearly, if the Int result of y has been computed, we must have examined all the elements in x. This implies we've forced the output stream. 

In Haskell, even with proper tail calls, this will infinite loop:

snd $ runState (sequence_ . repeat $ modify (1+)) 0

Under certain very restricted circumstances it might be possible to have traverse be lazier / more incremental. You would need:
* sequence would have to be implemented as a non-strict foldr (lift2 (:)) (pure []) supporting early termination
* to preserve the non-strictness of the above impl of sequence, lift2 would need to be non-strict in its second arg, and the applicative would have to take advantage of this - for state, I'm not sure this is even possible
* Assuming it were possible, State would have be non-strict in its argument type, and the particular state actions in question would have be take advantage of this. So, an Int state type is not going to work, since all the operations involving Ints are strict. 

I think with all these in place it might be possible to sequence an infinite stream of state actions or to sequence a finite stream in constant space. But it would be very delicate and error prone, and the compiler won't tell you if you've goofed up and been too strict somewhere (this would be true in Haskell as well). Which is why I don't think we should even try for scalaz - it would change a lot of type signatures and not buy us much.

StreamT[M,A] probably what you want. It is a stream where uncons yields an M[Option[(A,StreamT[M,A])]] (vs an Option[(A,Stream[A])] for a regular Stream), for some monad M (it is based on ListT done right). It functions a bit like an incremental traverse. I think of it as a kind of dual to monadic iteratees - many of the operations on Iteratee can be translated to StreamT operations without the inversion of control (filtering can be done by the Iteratee or by the StreamT source, mapping can be done by contramapping the Iteratee or mapping the StreamT, etc). 

We are using StreamT at work to generate and serialize large numbers of rows to a database while interleaving state action updates, all in constant space. It is pretty awesome. Unfortunately, it has pretty much zero documentation and there have been a couple minor fixes / additions that we've made locally to it that haven't been backported.* So it may not be ready for primetime.

Before scalaz 7 is released I'll try to make sure all the stuff we've done gets put in, and hopefully some docs get added.

Paul

[*]: If you are going to try using StreamT for your application, I think the main caveats are - foreach and toStream need to be specialized to Id to avoid stack overflows. We also added a couple helper functions: some of them are here. We have also noticed some issues with memory usage for certain scenarios that we haven't been able to pin down yet. If you do try using it and notice any memory usage weirdness (like something you expect to take constant memory is actually using up more), let me know.

Runar Bjarnason

unread,
Dec 4, 2011, 7:15:01 PM12/4/11
to sca...@googlegroups.com
As a side note, StreamT[M, A] can be modeled as Free[({type f[x] = M[(A, x)]})#f, Unit].

etorreborre

unread,
Dec 6, 2011, 2:44:04 AM12/6/11
to sca...@googlegroups.com
Thanks Paul for the write-up.

I'm eventually able to use traverse with State and my import messages get printed on the screen as expected. However I observe that the printing occurs only after a while, not as each line is read. The reason is that I'm sequencing a Seq[State] into a State[Seq] and that can't be done lazily as you wrote.

So I've been trying to use StreamT to do what I want, albeit unsuccessfully.

I've managed to create a StreamT by unfolding the lines iterator:

      val st = StreamT.unfoldM[({type l[a]=State[S, a]})#l, B, Seq[A]](seq: Seq[A]) { (ss: Seq[A]) =>
        if (!ss.isEmpty) f(ss.head).map((b: B) => Some((b, ss.tail)))
        else             state((s: S) => (s, None: Option[(B, Seq[A])]))
      }

This, however, gets me a SOE when I execute it. Does that mean that I need to trampoline the State as before?

If you have some time I'd appreciate any snippet of code pushing me to the right direction (I have no previous exposure to StreamT or ListT) for:

 - opening a file
 - be passed a function returning a State describing what to do for each line. More precisely I want to store the line in my db and write a message on the console, the message depends on the number of imported lines (hence the use of a State)
 - closing the file

Thanks,

Eric.





Paul Chiusano

unread,
Dec 6, 2011, 10:15:52 AM12/6/11
to sca...@googlegroups.com
Your unfoldM looks fine to me. Unless f(ss.head) is doing something that stack overflows I don't think you should have a problem unless there is something wrong with the unfoldM implementation (it also looks fine). StreamT should not require trampolining to avoid SOEs. 

What do you mean when you say you get a SOE "when you execute it"? What function on StreamT are you calling to get this SOE? As I mentioned in my email, the existing polymorphic foreach and toStream functions on StreamT are not safe to use - they will SOE for large StreamTs. You can write a specialized, tail recursive version of these functions for StreamT[Id,_], which is what we did for our application. I'll dig up those implementations for you if you are interested.

Paul

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To view this discussion on the web visit https://groups.google.com/d/msg/scalaz/-/WwMFHjw5oTcJ.

Runar Bjarnason

unread,
Dec 6, 2011, 11:56:55 AM12/6/11
to sca...@googlegroups.com
> - opening a file
> - be passed a function returning a State describing what to do for each line. More precisely I want to store the line in my db and write a message on the console, > the message depends on the number of imported lines (hence the use of a State)
> - closing the file"

None of that actually requires reifying the stream. You should never
have a Stream or a Seq in the first place. Here's something with
Iteratees:

val noop = ().pure[IO]

def processLines: Iteratee[IO, String, Unit] = {
def go(n: Int) = ContM((x: Input[String]) => Iteratee(step(n, x))).pure[IO]
def step(n: Int = 0, i: Input[String]): IO[IterVM[IO, String, Unit]]
= i match {
case El(e) => for {
_ <- putStrLn(e) // simulate database call
_ <- if (n % 10 == 0)
putStrLn("Processed " + n + " lines")
else noop
next <- go(n + 1)
} yield next
case Empty() => go(n)
case e@EOF() => DoneM((), e).pure[IO]
}
Iteratee(go(0))
}

type ProcessLines[A] = Iteratee[IO, String, A] => Iteratee[IO, String, A]

def processReaderLines[A](r: => BufferedReader): ProcessLines[A] = it => {
def loop(i: IterVM[IO, String, A]): IO[IterVM[IO, String, A]] = i.fold(
done = (_,_) => io { i },
cont = k => for {
s <- rReadLn(r)
a <- s.traverse(l => for {
v <- k(El(l)).value
x <- loop(v)
} yield x)
b <- a.map(_.pure[IO]).getOrElse(k(EOF[String]).value)
} yield b)
Iteratee(it.value >>= loop)
}

def processFileLines(f: File): Iteratee[IO] = it =>
Iteratee(bufferFile(f).bracket(closeReader)(processReaderLines(_)(it)))


Then you can say:

processFileLines(new File("myFile.txt"))(processLines).unsafePerformIO

On Tue, Dec 6, 2011 at 2:44 AM, etorreborre <etorr...@gmail.com> wrote:

> --
> You received this message because you are subscribed to the Google Groups
> "scalaz" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/scalaz/-/WwMFHjw5oTcJ.

Paul Chiusano

unread,
Dec 6, 2011, 12:26:57 PM12/6/11
to sca...@googlegroups.com
Note - I was mentioning earlier how you can express most computations either on the producer side (StreamT) or the consumer side (Iteratee). Runar is showing how you can do it on the consumer side. You could also do it on the producer side, by reifying the file lines as a StreamT[IO,String] (probably using unfoldM). You can then scanl or zip it with the StreamT 1,2,3..., then just foreach it. This approach might be more natural because you don't have to invert your thinking like you do with Iteratees. (I think sometimes it is more natural to think about expressing computations from the consumer side, and other times it's more natural to think about them from the producer side) 

You need some extra combinators that don't exist right now, but they are easy to write.

scanl for StreamT would take a (StreamT[M,A])(s: S)(f: (S,A) => (S,B)): StreamT[M,B] you can use this to add a line count to the input stream, or you could do this via zip, which doesn't exist right now but would have the obvious signature

You would also need a foreachIO: StreamT[IO,Unit] => IO[Unit]. This would return an IO action that, in a while loop, peeled off IO actions from the streamT and unsafePerformIO'd them

Paul

etorreborre

unread,
Dec 6, 2011, 6:19:48 PM12/6/11
to sca...@googlegroups.com
One more question: is that possible to write a tail-recursive version of StreamT[M, A].toStream when M is a general monad (not Id)?

E.


Runar Oli

unread,
Dec 6, 2011, 6:46:51 PM12/6/11
to sca...@googlegroups.com, sca...@googlegroups.com
Only if M is is a Free monad.


On Dec 6, 2011, at 18:19, etorreborre <etorr...@gmail.com> wrote:

One more question: is that possible to write a tail-recursive version of StreamT[M, A].toStream when M is a general monad (not Id)?

E.


--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To view this discussion on the web visit https://groups.google.com/d/msg/scalaz/-/LhPXX5xlrVsJ.

etorreborre

unread,
Dec 6, 2011, 7:20:35 PM12/6/11
to sca...@googlegroups.com
> Only if M is is a Free monad.

I need to read up on that. I've seen that you've renamed Coroutine to Free but I don't understand yet the theory behind all that.

For the record, I've written the following for toStream, as Paul suggested:

    private def toStream[A](streamT: StreamT[Id, A]): Stream[A] = toStream(streamT, Stream.Empty)

    @tailrec
    private def toStream[A](streamT: StreamT[Id, A], result: Stream[A]): Stream[A] =
      streamT.uncons match {
        case Some((head, tail)) => toStream(tail, Stream.cons(head, result))
        case None               => result
      }

And, in passing, I think I found a bug: https://github.com/scalaz/scalaz/issues/57.

Eric.

Paul Chiusano

unread,
Dec 7, 2011, 12:13:41 AM12/7/11
to sca...@googlegroups.com

Can you elaborate? I thought it might be possible via trampoline. What is the tail recursive implementation for the free monad?

Runar Bjarnason

unread,
Dec 7, 2011, 8:59:25 AM12/7/11
to sca...@googlegroups.com
In Scalaz, speficially. Free is implemented with three constructors,
one of which represents monadic bind. So flatMaps are not function
calls, but constructor calls, so they don't accumulate stack.

Runar

Reply all
Reply to author
Forward
0 new messages