How can I create an alternating infinite stream?

Question

I want to create an infinite stream of chars like so:

I start with "" and some chars, let's say "abc".

How exactly do I end up with the infinite stream that looks like this:

["", "a", "b", "c", "aa", "ba", "ca", "ab", ..]

The basic logic would be to take last elements of highest length and add each of the chars from my initial list "abc" to them and repeat. However, I'm not sure if this is the right way to do things in Haskell (seems more like a procedural solution of the problem).

My first attempt was to create the stream given only one element so I made a stream of a's:

let as = iterate ((++) "a") ""

This works, but I am not sure how this could evolve so that I can get the first stream.

Answer 1

Here's a solution that does use iterate.

import Control.Applicative
gen = [(++ "a"), (++ "b"), (++ "c")]
expand v = concatMap (<$> v) gen
v = concat $ iterate expand [""]

The tricky part is expand. It's a condensed version of the slightly more readable function

expand v = concat [ fmap f v | f <- gen ]

which appends each letter of your generator to each string in a list. Looking at the first few iterations,

expand [""] = ["a", "b", "c"]
expand ["a", "b", "c"] = ["aa", "ba", "ca", "ab", "bb", "cb", "ac", "bc", "cc"]

The iterate command ties it together by producing the infinite list of lists [ [""], expand [""], expand . expand $ [""], ...].

Answer 2

Let's say we have already a list of strings like ["", "a", "b", "c"]. How can we produce the next elements from that string? Well, we can take every element and add 'a', 'b' and 'c' in front of it:

Prelude> concatMap (\xs -> ['a' : xs, 'b' : xs, 'c' : xs]) ["", "a", "b", "c"]
["a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc"]

Seems good so far. Let's give that a name:

step :: [String] -> [String]
step = concatMap (\xs -> ['a' : xs, 'b' : xs, 'c' : xs])

We can now define our infinite stream recursively with a base value and step:

stream :: [String]
stream = "" : step stream

Answer 3

Well iterate has some useful concepts but in and of itself isn't going to take you to a solution. What you should probably do is recognize your pattern and build from there.

"" , a: "", b : "", c : "", a: a:"", b : a : "", c : a : "", a : b : ""

So clearly we have a base case of "" and three modifier functions of 'a':, 'b': and 'c':. Let's write that down!

mods :: [String -> String]
mods = [ (x:) | x <- "abc" ]

strings :: [String]
strings = baseCase : stringsRecursiveCase
 where baseCase = ""

What is the recursive case? Well you took the most recent string and applied each of the modifier functions one at a time:

stringsRecursiveCase = [ f s | s <- strings , f <- mods ]

Now we can test to observe and verify the functionallity:

take 15 strings
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa"]