Function that produces \$a^nb^nc^n\$

Question

I'm trying to write a function that produces an infinite list containing strings of the form \$a^nb^nc^n\$.

My first idea was to do it using comprehensions.

f = [replicate n 'a' ++ replicate n 'b' ++ replicate n 'c' | n <-[0..]]

But this does a lot of duplicate work. I then decided it would be better to do the following

import Data.List

f = "" : (abc "")

abc s = string : (abc string)
        where string = sort $ "abc" ++ s 

How can I do this more efficiently without having to sort and use ++ as frequently? Would changing to ByteStrings help?

Answer 1

Your first solution could be more elegantly written as:

f :: [String]
f = [concatMap (replicate n) "abc" | n <- [0..]]

The basic operating principle would be the same, though.

A general sorting algorithm would be O(n log n) at best, so I don't believe that sort would be a good idea.

Answer 2

I was suspicious that your initial code was basically as good as possible. It's already algorithmically better than your second example. String is immutable linked list. There's no way sorting String values is better than just generating the correct values in the first place.

So, I decided to benchmark your initial version vs a hand-fused version that is guaranteed to allocate only exactly what it needs.

module Main where

import Criterion.Main


naive :: Int -> [String]
naive n = [ r 'a' ++ r 'b' ++ r 'c' | i <- [1..n], let r = replicate i ]


fused :: Int -> [String]
fused n | n < 1     = []
        | otherwise = go 1
  where
    go i | i == n    = [abcs 1]
         | otherwise = abcs 1 : go (i + 1)
      where
        abcs j | j == i    = 'a' : bcs 1
               | otherwise = 'a' : abcs (j + 1)
        bcs j  | j == i    = 'b' : cs 1
               | otherwise = 'b' : bcs (j + 1)
        cs j   | j == i    = "c"
               | otherwise = 'c' : cs (j + 1)


main :: IO ()
main = defaultMain [ bench "naive" $ nf naive 100
                   , bench "fused" $ nf fused 100
                   ]

I changed the definitions to be functions that take the max size instead of infinite lists in order to prevent memoization from breaking the benchmarks.

Here are the results I got:

benchmarking naive
time                 188.4 μs   (184.6 μs .. 192.9 μs)
                     0.996 R²   (0.993 R² .. 0.997 R²)
mean                 191.4 μs   (187.8 μs .. 195.8 μs)
std dev              12.96 μs   (10.57 μs .. 16.39 μs)
variance introduced by outliers: 64% (severely inflated)

benchmarking fused
time                 190.2 μs   (186.3 μs .. 194.7 μs)
                     0.996 R²   (0.994 R² .. 0.997 R²)
mean                 191.5 μs   (187.8 μs .. 197.0 μs)
std dev              15.01 μs   (11.23 μs .. 22.43 μs)
variance introduced by outliers: 71% (severely inflated)

And the results say... They run in basically exactly the same time. The differences are well within the standard deviations in the measurements, and my computer is apparently a very noisy system to benchmark on.

The conclusion I draw from this is that the naive code is basically as good as possible. The optimizations present in GHC and its libraries make it exactly as good as the far-more-complicated fully hand-fused implementation.

---

The effect of sharing

Some comments on the question reminded me that sharing is possible in this problem, to some small extent. In particular, the suffix of 'c' characters can be shared from one list entry to the next.

share :: Int -> [String]
share n | n < 1     = []
        | otherwise = go 1 "c"
  where
    go i cs | i == n    = [abcs 1]
            | otherwise = abcs 1 : go (i + 1) ('c' : cs)
      where
        abcs j | j == i    = 'a' : bcs 1
               | otherwise = 'a' : abcs (j + 1)
        bcs j  | j == i    = 'b' : cs
               | otherwise = 'b' : bcs (j + 1)

So is this better? Well - it depends. It should be better when the cost of allocating the suffixes is higher than the cost of keeping them around. The memory use of keeping them in memory isn't insignificant. Eventually it starts to really make a difference.

Here's a new set of benchmarks:

module Main where

import Criterion.Main


naive :: Int -> [String]
naive n = [ r 'a' ++ r 'b' ++ r 'c' | i <- [1..n], let r = replicate i ]


fused :: Int -> [String]
fused n | n < 1     = []
        | otherwise = go 1
  where
    go i | i == n    = [abcs 1]
         | otherwise = abcs 1 : go (i + 1)
      where
        abcs j | j == i    = 'a' : bcs 1
               | otherwise = 'a' : abcs (j + 1)
        bcs j  | j == i    = 'b' : cs 1
               | otherwise = 'b' : bcs (j + 1)
        cs j   | j == i    = "c"
               | otherwise = 'c' : cs (j + 1)


share :: Int -> [String]
share n | n < 1     = []
        | otherwise = go 1 "c"
  where
    go i cs | i == n    = [abcs 1]
            | otherwise = abcs 1 : go (i + 1) ('c' : cs)
      where
        abcs j | j == i    = 'a' : bcs 1
               | otherwise = 'a' : abcs (j + 1)
        bcs j  | j == i    = 'b' : cs
               | otherwise = 'b' : bcs (j + 1)


main :: IO ()
main = defaultMain [ bench "naive" $ nf naive 100
                   , bench "fused" $ nf fused 100
                   , bench "share" $ nf share 100
                   , bench "naive/deep" $ nf (last . naive) n
                   , bench "fused/deep" $ nf (last . fused) n
                   , bench "share/deep" $ nf (last . share) n
                   ]
  where
    n = 100000

Note that I do a round of benchmarks forcing smaller values fully into memory, and then do a second round of benchmarks with a much larger value that I only care about the last entry of.

Here are the results:

benchmarking naive
time                 197.5 μs   (193.0 μs .. 201.7 μs)
                     0.996 R²   (0.994 R² .. 0.998 R²)
mean                 198.5 μs   (194.4 μs .. 202.4 μs)
std dev              13.41 μs   (10.92 μs .. 16.25 μs)
variance introduced by outliers: 64% (severely inflated)

benchmarking fused
time                 187.6 μs   (182.8 μs .. 193.5 μs)
                     0.995 R²   (0.993 R² .. 0.997 R²)
mean                 193.1 μs   (189.5 μs .. 197.4 μs)
std dev              13.36 μs   (10.52 μs .. 17.51 μs)
variance introduced by outliers: 65% (severely inflated)

benchmarking share
time                 163.8 μs   (161.0 μs .. 166.6 μs)
                     0.997 R²   (0.995 R² .. 0.998 R²)
mean                 161.8 μs   (159.2 μs .. 164.4 μs)
std dev              9.084 μs   (7.734 μs .. 10.85 μs)
variance introduced by outliers: 56% (severely inflated)

benchmarking naive/deep
time                 7.928 ms   (7.712 ms .. 8.136 ms)
                     0.995 R²   (0.991 R² .. 0.997 R²)
mean                 7.937 ms   (7.820 ms .. 8.118 ms)
std dev              423.0 μs   (293.4 μs .. 666.7 μs)
variance introduced by outliers: 28% (moderately inflated)

benchmarking fused/deep
time                 8.650 ms   (8.349 ms .. 8.961 ms)
                     0.993 R²   (0.989 R² .. 0.997 R²)
mean                 8.559 ms   (8.432 ms .. 8.675 ms)
std dev              341.4 μs   (282.5 μs .. 420.7 μs)
variance introduced by outliers: 18% (moderately inflated)

benchmarking share/deep
time                 12.81 ms   (12.49 ms .. 13.17 ms)
                     0.996 R²   (0.993 R² .. 0.998 R²)
mean                 13.43 ms   (13.08 ms .. 14.34 ms)
std dev              1.356 ms   (553.3 μs .. 2.492 ms)
variance introduced by outliers: 52% (severely inflated)

Wow, my machine is noisy. I don't really know why it's that bad, but moving on..

The version that explicitly shares tails performs better in the small test, by a notable margin. At those sizes, the memory use doesn't have a significant performance impact.

But in the larger test, it's notably slower. At that size, the cost of the additional memory use is visible.

A side note from the larger test is that the performance difference between the naive version and my hand-fused version has become significant, and the hand-fused version is slower. I'm not as good of an optimizer as GHC! (I suspect that the issue is that I'm counting up and comparing against a non-zero value in my loops. I could test, but that's getting pretty far-afield.)

In summary, I'd use the naive version. It might be a little slower in small cases, but when things get big, it starts to get ahead. And it definitely has better properties about memory use at any size. Sometimes duplicating work is faster than caching it.