Haskell Tabulate function using Foldmap "Out of Scope"

Question

I am trying to write a definition for "tabulate", a function that produces the monoidal summary of the values in the given Map that correspond to the keys in the given Foldable collection.

Here is my code:

module Foldables where

import Prelude hiding (Applicative(..), any, concat)
import Data.Foldable
import Data.Semigroup

import qualified Data.Map as Map
import Data.Map (Map)
import Data.Map.Append (AppendMap(..))
import Data.List (intersperse)
import Data.Maybe (maybe)
import Data.Monoid (Any(..), Sum(..))
import GHC.Generics (Generic)

tabulate :: (Ord k, Foldable f, Monoid a) => (v -> a) -> Map k v -> f k -> a
tabulate t m = foldMap (tabulate . k v)

I am getting this error:

src/Foldables.lhs:295:27: error:
    • Data constructor not in scope: Tabulate :: b0 -> a
    • Perhaps you meant variable ‘tabulate’ (line 295)

src/Foldables.lhs:295:38: error:
    Variable not in scope: k :: t0 -> k -> b0

Please don't change anything but what's in the parenthesis on the second line

Update: I think I'm closer to understanding this. Here is my new code. I realize it's incomplete, but it at least compiles.

tabulate :: (Ord k, Foldable f, Monoid a) => (v -> a) -> Map k v -> f k -> a
tabulate t m = foldMap (\x -> mempty maybe [m] maybe map [t])

Now it fails a cabal test:

   Falsified (after 2 tests):
     <fun>
     fromList [(False,'\DC4'),(True,'\1054302')]
     [True,True]

No matter what I do seem to get some variation of that

I'm assuming what I need is some kind of conditional in the event the third argument of tabulate isn't mempty?

Answer 1

Here is a hint (that is a solution without foldMap, which I reckon to be the object of the problem):

If I get you correctly, you want to write down something like this:

tabulate :: (Ord k, Foldable t, Monoid a) => (v -> a) -> Map k v -> t k -> a
tabulate t m ks = let
                    c k x = (t <$> Data.Map.Strict.lookup k m) <> x
                  in case Prelude.foldr c Nothing ks of
                          Just s  -> s
                          Nothing -> mempty

The case I wrote down is there to work when the intersection of ks (by the way, a solution with foldMap would not need this argument - it will be dropped, as you wanted in the post) with the keys of the map (m) is empty (that is, only Nothings were gathered).

In other cases, we just fold the container of keys with something, resembling mappend for Maybe - it first tries to look the given key up in the map. If it succeeds, it puts the result into Just and then fmaps the transformation t (which gives us a monoid) into it. If it does not, it returns Nothing. In the mappend-sequence of Maybes all Nothings get discarded and the results inside Justs get concatenated with mappend. See the defintion of <> for Maybe (<> is Semigroup's method, which underlies mappend as Monoid is Semigroup's subclass):

-- | @since 4.9.0.0
instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> b       = b
    a       <> Nothing = a
    Just a  <> Just b  = Just (a <> b)
    ...

---

My solution with foldMap:

tabulate :: (Ord k, Foldable t, Monoid a) => (v -> a) -> Map k v -> t k -> a
tabulate t m = foldMap (\ k -> maybe mempty t (Data.Map.Strict.lookup k m))

It does the following: the function-argument of foldMap takes a key k. If it's not in the map, it returns mempty. Otherwise - it returns t x, where Just x is what the lookup got.