Using an Array in a List Comprehension?

Question

I am working through The Pearls of Functional Algorithm Design book. I am having issues with a provided example. In the book, the author uses an array in a list comprehension like so:

countlist :: [Int] → Array Int Int
countlist xs = accumArray (+) 0 (0, n ) (zip xs (repeat 1))

sort xs = concat [replicate k x | (x,k)←countlist xs]

I've then transposed this (with minimal modification) into real runnable code:

countlist :: [Int] -> Array Int Int   
countlist xs = accumArray (+) 0 (0, n)(zip xs (repeat 1))
               where n = length xs 

sortLinearTime :: [Int] -> [Int]
sortLinearTime xs = concat [replicate k x | (x, k) <- countlist xs]

This however does not compile with:

Couldn't match expected type ‘[(Int, Int)]’
                  with actual type ‘Array Int Int’
    • In the expression: countlist xs
      In a stmt of a list comprehension: (x, k) <- countlist xs
      In the first argument of ‘concat’, namely
        ‘[replicate k x | (x, k) <- countlist xs]’

Using ghci to construct a minimal example:

import Data.Array
let arr = accumArray (+) 0 (0, 7) [(0,1),(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)]
[x | (k, x) <- arr]

Which results in:

Couldn't match expected type ‘[(t0, t)]’
            with actual type ‘Array Integer Integer’
Relevant bindings include it :: [t] (bound at <interactive>:38:1)
In the expression: arr
In a stmt of a list comprehension: (k, x) <- arr

So how is it possible for me to use a Data.Array in a list comprehension?

Answer 1

I believe you're looking for indices, elems or assoc:

Prelude> import Data.Array
Prelude Data.Array> let arr = accumArray (+) 0 (0, 7) [(0,1),(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)]
Prelude Data.Array> indices arr
[0,1,2,3,4,5,6,7]
Prelude Data.Array> elems arr
[1,1,1,1,1,1,1,0]
Prelude Data.Array> [2*k + x | (k, x) <- assocs arr]
[1,3,5,7,9,11,13,14]

The last one shows you how to write a generic list comprehension.

For more information, you should consult the documentation of Data.Array.