Exponentiation using list comprehension

Question

I'm trying to solve the following exercise (I'm learning Haskell):

Define x^n using a list comprehension.

And I'm struggling to find a solution.

Using recursion or fold, the solution is not complicated (for instance, foldr (*) 1 [x | c <- [1..n]]). However, using only list comprehension it gets difficult (at least for me).

In order to solve the problem, I'm trying to create a list of x^n elements and then get the length. Generating a list of x*n elements is easy, but I fail to generate a list of x^n elements.

ppower x n = length [1 | p <- [1..x], c <- [1..n]]

returns a list of x*n elements giving a wrong result. Any ideas on this will be appreciated.

Answer 1

A naturally-occurring exponential comes from sequence:

length (sequence [[1..x] | _ <- [1..n]])

If you haven't seen sequence yet, it's quite a general function but when used with lists it works like:

sequence [xs1, ... , xsk] = [[x1, ... xk] | x1 <- xs1, ... , xk <- xsk]

But this is really cheating since sequence is defined recursively.

---

If you want to use nothing but length and list comprehensions I think it might be impossible. The rest of this answer will be sketchy and I half expect someone to prove me wrong. However:

We'll try to prove that such an expression can only compute values up to some finite power of x or n, and therefore can't compute values as big as x^n for arbitrary x and n.

Specifically we show by induction on the structure of expressions that any expression expr has an upper bound ub(expr, m) = m^k where m is the maximum of the free variables it uses, and k is a known finite power which we could calculate from the structure of the expression expr.

(When we look at the whole expression, m will be max x n.)

Our upper bounds on list expressions will be bounds on both the length of the list and also bounds on any of its elements (and lengths of its elements, etc.).

For example if we have [x..y] and we know that x <= m and y <= m, we know that all the elements are <= m and the length is also <= m. So we have ub([x..y], m) = m^1.

The tricky case is the list comprehension:

[eleft | x1 <- e1, ... , xk <- ek]

The result will have length equal to length e1 * ... * length ek, so an upper bound for it would be the product of the upper bounds for e1 to ek, or if m^i is the maximum of these then an upper bound would be (m^i)^k = m^(i*k).

To get a bound on the elements, suppose expression eleft has ub(eleft, m') = m'^j. It can use x1 ... xk. If m^i is an upper bound for these, as above, we need to take m' = m^i and so ub(eleft, m) = (m^i)^j = m^(i*j)

As a conservative upper bound for the whole list comprehension e we could take ub(e, m) = m^(i*j*k).

I should really also work through cases for pattern matching (shouldn't be a problem because the parts matched are smaller than what we already had), let definitions and functions (but we banned recursion, so we can just fully expand these before we start), and list literals like [x,37,x,x,n] (we can throw their lengths into m as initially-available values).

If infinite lists like [x..] or [x,y..] are allowed they would need some thinking about. We can construct head and filter, which means we can get from an infinite list to its first element matching a predicate, and that looks suspiciously like a way to get recursive functions. I don't think it's a problem since 1. they are only arithmetic sequences and 2. we'll have to construct any numbers we want to use in the predicate. But I'm not certain here.