title: Memoizing multiplication
body: <p>My application multiplies vectors after a (costly) conversion using an FFT. As a result, when I write </p>
  
  <pre><code>f :: (Num a) =&gt; a -&gt; [a] -&gt; [a]
  f c xs = map (c*) xs
  </code></pre>
  
  <p>I only want to compute the FFT of <code>c</code> once, rather than for every element of <code>xs</code>. There really isn't any need to store the FFT of <code>c</code> for the entire program, just in the local scope.</p>
  
  <p>I attempted to define my <code>Num</code> instance like:</p>
  
  <pre><code>data Foo = Scalar c
           | Vec Bool v -- the bool indicates which domain v is in
  
  instance Num Foo where
      (*) (Scalar c) = \x -&gt; case x of
                           Scalar d -&gt; Scalar (c*d)
                           Vec b v-&gt; Vec b $ map (c*) v
      (*) v1 = let Vec True v = fft v1
               in \x -&gt; case x of
                      Scalar d -&gt; Vec True $ map (c*) v
                      v2 -&gt; Vec True $ zipWith (*) v (fft v2)
  </code></pre>
  
  <p>Then, in an application, I call a function similar to <code>f</code> (which works on arbitrary <code>Num</code>s) where <code>c=Vec False v</code>, and I expected that this would be just as fast as if I hack <code>f</code> to:</p>
  
  <pre><code>g :: Foo -&gt; [Foo] -&gt; [Foo]
  g c xs = let c' = fft c
           in map (c'*) xs
  </code></pre>
  
  <p>The function <code>g</code> makes the memoization of <code>fft c</code> occur, and is much faster than calling <code>f</code> (no matter how I define <code>(*)</code>). I don't understand what is going wrong with <code>f</code>. Is it my definition of <code>(*)</code> in the <code>Num</code> instance? Does it have something to do with <code>f</code> working over all Nums, and GHC therefore being unable to figure out how to partially compute <code>(*)</code>?</p>
  
  <p><em>Note</em>: I checked the core output for my Num instance, and (*) is indeed represented as nested lambdas with the FFT conversion in the top level lambda. So it looks like this is at least capable of being memoized. I have also tried both judicious and reckless use of bang patterns to attempt to force evaluation to no effect.</p>
  
  <p>As a side note, even if I can figure out how to make <code>(*)</code> memoize its first argument, there is still another problem with how it is defined: A programmer wanting to <em>use</em> the Foo data type has to know about this memoization capability. If she wrote</p>
  
  <pre><code>map (*c) xs
  </code></pre>
  
  <p>no memoization would occur. (It must be written as <code>(map (c*) xs))</code> Now that I think about it, I'm not entirely sure how GHC would rewrite the <code>(*c)</code> version since I have curried <code>(*)</code>. But I did a quick test to verify that both <code>(*c)</code> and <code>(c*)</code> work as expected: <code>(c*)</code> makes <code>c</code> the first arg to <code>*</code>, while <code>(*c)</code> makes <code>c</code> the second arg to <code>*</code>. So the problem is that it is not obvious how one should write the multiplication to ensure memoization. Is this just an inherent downside to the infix notation (and the implicit assumption that the arguments to <code>*</code> are symmetric)?</p>
  
  <p>The second, less pressing issue is that the case where we map (v*) onto a list of <em>scalars</em>. In this case, (hopefully) the fft of v would be computed and stored, even though it is unnecessary since the other multiplicand is a scalar. Is there any way around this?</p>
  
  <p>Thanks</p>