Normalize away unnecessary `Compose` and `Identity` nested in a type-CodePudding

I'd like to define a type which contains a container and a type for the container, and some operations, like one to perform an outer-product on the containers, one to map the container and its value, as well as everything offered by various standard classes (Functor, Applicative, Monad, MonadTrans etc).

This is the definition of the type and the two operations I mentioned:

-- metacontainer
newtype MC c a = MC { runMetaContainer :: c a } deriving Show

-- outer product
cross :: (Functor f1, Functor f2) => (a -> b -> c) -> MC f1 a -> MC f2 b
  -> MC (Compose f1 f2) c
cross f (MC c1) (MC c2) = MC $ Compose $ (\x -> f x <$> c2) <$> c1

-- map the container
hoist :: (c1 a -> c2 b) -> MC c1 a -> MC c2 b
hoist f (MC c) = MC $ f c

This stuff works, however when I cross two MCs, the resulting container is made of some nested unnecessary containers, such as Compose or Identity. I wish to get rid of them somehow.

See this example:

let list = MC [1,2,3]          :: MC [] Int
let justStr = MC $ Just "hey"  :: MC Maybe String
let n = MC $ Identity 5        :: MC Identity Int

let dblLst = cross (*) list n  :: MC (Compose [] Identity) Int
let justStrList = cross (\x str -> str    " "    show x)
  dblLst justStr               :: MC (Compose (Compose [] Identity) Maybe) String

Because of those unnecessary Composes and Identitys in justStrList's type, I cannot simply do something like...

hoist (\lstMbStr -> lstMbStr & filter isJust & map fromJust) justStrList
-- error
--     • Couldn't match type ‘Compose (Compose [] Identity) Maybe’
--                      with ‘[]’
--       Expected: MyType [] (Maybe b0)
--         Actual: MyType (Compose (Compose [] Identity) Maybe) String

Is there any way to normalize a container?

In case of the example I'd like to turn the (Compose (Compose [] Identity) Maybe) String into the equivalent [Maybe String].

I tried to use Li-yao Xia's solution, but it's not working for me.

This is my entire code:

import Data.Maybe ( catMaybes )
import Data.Functor.Identity ( Identity(..) )
import Data.Functor.Compose ( Compose, Compose(..) )
import Data.Coerce (coerce, Coercible)

-- metacontainer
newtype MC c a = MC { runMetaContainer :: c a }

-- outer product
cross :: (Functor f1, Functor f2) => (a -> b -> c) -> MC f1 a -> MC f2 b
  -> MC (Compose f1 f2) c
cross f (MC c1) (MC c2) = MC $ Compose $ (\x -> f x <$> c2) <$> c1

-- map the container
hoist :: (c1 a -> c2 b) -> MC c1 a -> MC c2 b
hoist f (MC c) = MC $ f c

coerceMC :: Coercible (c a) (d a) => MC c a -> MC d a
coerceMC = coerce

main :: IO ()
main = do
    let list = MC [1,2,3]
    let justStr = MC $ Just "hey"
    let n = MC $ Identity 5

    let dblLst = cross (*) list n
    let justStrList = cross (\x str -> str    " "    show x) dblLst justStr
    
    print $ hoist catMaybes (coerceMC justStrList)

And this is the error I'm receiving:

error:
    • Couldn't match type: [Char]
                     with: Maybe b0
      Expected: MC (Compose (Compose [] Identity) Maybe) (Maybe b0)
        Actual: MC (Compose (Compose [] Identity) Maybe) [Char]
    • In the first argument of ‘coerceMC’, namely ‘justStrList’
      In the second argument of ‘hoist’, namely ‘(coerceMC justStrList)’
      In the second argument of ‘($)’, namely
        ‘hoist catMaybes (coerceMC justStrList)’

If I try to ask GHC for the type of coerceMC justStrList, it says it's MC d0 [Char] where ‘d0’ is an ambiguous type variable.

If I try to enable the PartialTypeSignatures extension, it says that it can't match representation of type: [Identity (Maybe [Char])] with that of: d0 [Char].

I wouldn't know how to express by myself the type that I wish coerceMC justStrList has. It would be MC [Maybe] String, except that it's not a valid type due to mismatching kinds.

I tried to coerce the container inside of the hoist function (hoist f (MC c) = MC $ f $ coerce c) since I would know how to express the coercion for c (from Compose (Compose [] Identity) Maybe String to [Maybe String]), but it still doesn't work.

I managed to get it to work with this definition of hoist: hoist f (MC c) = MC $ f (coerce c :: [Maybe String]), but I wish to find a solution that can infer the coercion type from the type of f, if it can exist.

CodePudding user response：

You can use coerce to map between types with the same run-time representation.

import Data.Coerce (coerce, Coercible)

-- Example specialization
example :: MC (Compose (Compose [] Identity) Maybe) a -> MC (Compose [] Maybe) a
example = coerce

coerce is very polymorphic and usually requires type annotations. The following specialization may help by fixing some of the type parameters:

coerceMC :: Coercible (c a) (d a) => MC c a -> MC d a
coerceMC = coerce

Your example still requires a bit more complexity. The type of justStrList is MC (Compose (Compose [] Identity) Maybe) String, which simplifies to MC (Compose [] Maybe) String, still with some Compose left, and this cannot really be simplified further.

Indeed, that last Compose can only be eliminated in hoist, just before applying the given function. It's a bit tricky to find a nice enough generalization of hoist. I would opt for this one, that just takes some conversion functions surrounding the main one.

hoistBetween :: (c1 a -> x) -> (y -> c2 b) -> (x -> y) -> MC c1 a -> MC c2 b
hoistBetween f h g (MC c) = MC $ h (g (f c))

You probably do not want both to be coerce because of the type inference issues mentioned earlier. A more specialized combinator which applies coerce on once side would have an ugly, asymmetrical signature. So hoistBetween it is.

You can now write this:

    print (hoistBetween coerce id catMaybes justStrList :: MC [] String)

This still requires a type signature on the result, because print is polymorphic, but in more substantial examples you can probably rely on both sides of hoistBetween to be known.

Alternatively, this hoistBetween lets you also just use the newtype constructors and destructors, avoiding the type inference issues of coerce (for a bit of overhead).

    print (hoistBetween
             (fmap runIdentity . getCompose . getCompose)
             id
             catMaybes
             justStrList)