Java FoldMap Lists, or “how to get around the lazy/eager dissonance”

Question

I am porting this package to Java and have gotten stuck trying to get around the lazy/eager dissonance between the two languages. I didn't think it was going to be as severe as it is because the implementation depends entirely on function types, but I guess I was wrong. How do I preserve enough laziness for this to work? Alternatively, how do I minimally rewrite this so that it becomes eager enough for Java?

The Code

Available directly on pastebin now, thanks for telling me.

InfiniteListException.java

TransformFunc.java

TransformCSFunc.java

FM.java

FMList.java

The Problem

I get a stack overflow (heh) on almost every "functional-style" method, and force() has to be called almost constantly in order to prevent them even when not coding functionally.

Answer 1

You are going to hate my answer, as it is just a real pain to convert code from a functional language to an imperative one, even if it doesn't appear so up front.

There are basically two things you can do:

1. Rewrite to remove the recursion. This isn't always possible, nor is it easy. Sometimes, there is an algorithm to do so (the only one I can think of off the top of my head, is when the function is tail recursive, but there might be more). Other times, you have to do the work yourself and write a custom function that does the same as the original, but does so without using recursion.

2. You can build your own call stack-like system to use instead of the call stack the language is using. This allows you to do optimizations functional languages do on it, but imperative ones don't, it allows you to have a stack per function, which does reduce the chance of running out of stack and it also allows you to have a stack of the size you like.

Of course, you can combine to the two techniques as much as you want to, as basically you will need a solution to every single function used in the script.

As I said, it's not good news. It's pretty sucky news, as this means there is a whole lot of work ahead if you want to port this (or any other) functional library to imperative world.

Answer 2

I am unfamiliar with FoldMap, but some of functional-java's List functions (also Arrays and Streams) are implemented internally using a constant stack space, check out foldLeft and foreach for example, maybe they can help..

Answer 3

An unconvential way would be to compile the slightly modified Haskell source code with Frege.

Modifications needed are often confined to the export list (Frege has none) and imports.