1

I'm trying to memoize this function with an array:

a n 0 = n
a n k = a (2*n - 1) (k - 1) / a (2*n) (k - 1)

I've done this:

import Data.Array

cache :: (Ix a, Real b) => Array a [(a, b)]
cache = array bounds [(i, func i) | i <- range bounds]
    where bounds = ((0,0), (1000, 1000))
          func elem =
            let f n 0 = n
                f n k = f (2*n - 1) (k - 1) / f (2*n) (k - 1)
             in uncurry f elem

a n k = cache!(n,k)

GHCi fails with this error:

aarr.hs:6:16:
    Could not deduce (a ~ ([(a, b)], b0))
    from the context (Ix a, Real b)
      bound by the type signature for
                 values :: (Ix a, Real b) => Array a [(a, b)]
      at aarr.hs:5:11-44
      ‘a’ is a rigid type variable bound by
          the type signature for values :: (Ix a, Real b) => Array a [(a, b)]
          at aarr.hs:5:11
    Expected type: (a, a)
      Actual type: (([(a, b)], b0), ([(a, b)], b0))
    Relevant bindings include
      bounds :: (([(a, b)], b0), ([(a, b)], b0)) (bound at aarr.hs:7:11)
      values :: Array a [(a, b)] (bound at aarr.hs:6:1)
    In the first argument of ‘array’, namely ‘bounds’
    In the expression: array bounds [(i, func i) | i <- range bounds]

My head is spinning from all the type errors (and infinite type ones) I got... I thought this could work.

Improve this question
2
  • The type of range is range :: Ix a => (a, a) -> [a] and you're giving it ((a,a),(a,a)). Read the last 2 lines of ghci's output: In the first argument of ‘array’, namely ‘bounds’ In the expression: array bounds [(i, func i) | i <- range bounds] Commented Sep 9, 2014 at 16:03
  • But in GHCi this works: Prelude Data.Array> range ((0, 0), (3, 3)) [(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3)]. I think (0, 0) is an instance of Ix too. Commented Sep 9, 2014 at 16:10

1 Answer 1

Reset to default
3

The Problem

There are two problems with your your cache function which are preventing it from compiling.

The first is that the type of (/) is as follows,

(/) :: Fractional a => a -> a -> a

However the compiler is inferring the values in your bounds as Integral types, which is doesn't jive with your use of /.

The second is that your type signature is incorrect.

A Solution

There are a number of ways to correct this, but probably the simplest is the following,

cache :: (Ix b, Fractional b) => Array (b, b) b
cache = array bounds [(i, func i) | i <- range bounds]
    where bounds = ((0.0,0.0), (1000.0, 1000.0))
          func elem =
            let f n 0 = n
                f n k = f (2*n - 1) (k - 1) / f (2*n) (k - 1)
             in uncurry f elem

Notice that the values of bounds are now Fractional values.

Also notice that I changed your type signature. The first type parameter to Array needs to be the Ix instance. Since you are using Fractional pairs as the indices this needs to be reflected in the type. Secondly, this also means that the values of the element in the array, shares the same type as the index. If you wish to have you index be an Integral value, then you could do the following,

cache :: (Integral a, Ix a, Fractional b) => Array (a, a) b
cache = array bounds [(i, func i) | i <- range bounds]
    where bounds = ((0,0), (1000, 1000))
          func (a, b) =
            let f n 0 = n
                f n k = f (2*n - 1) (k - 1) / f (2*n) (k - 1)
             in uncurry f (fromIntegral a, fromIntegral b)

Note, I don't know if using an Integral type vs. a Fractional type as the index has any performance considerations as I don't use the Array type very often.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Wow, thank you for taking the time to write this. I now see the problems with my code. I'll check Map as well, or try to solve the recursion. Just one thing: shouldn't (\) be (/)? Thanks again!
It should. Good catch.
I may be incorrect about the strictness of the Array. I was just reading the documentation for it and it claims, "Because the indices must be checked for these errors, array is strict in the bounds argument and in the indices of the association list, but non-strict in the values." Which means it would have to fully compute the bounds and indices but not the values.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.