Converting Rose (Board, Int) to Rose Int through Functor instance-CodePudding

data Rose a = MkRose a [Rose a]
    deriving (Eq, Show)

-- Rose Int with two children
t1 = MkRose 3 [MkRose 9 [], MkRose 2 []]

data Field = X | O | B
    deriving (Eq, Ord)

type Row   = (Field, Field, Field)
type Board = (Row, Row, Row)

minimax :: Player -> Rose Board -> Rose Int 
-- MkRose -1 [MkRose 1 [..], MkRose -1 [..], MkRose 1 [..] ]
minimax P1 (MkRose b bs)
  = let bs' = minimax' (MkRose b bs) 
-- :t bs' = MkRose (Board, Int) 
--            [MkRose (Board,Int) [], MkRose (Board,Int) [] ]
    in  fmap snd bs'

If I have a Rose (Board, Int), I want to be able to convert it to just a Rose Int. I switched from attempting a Functor instance to just using fmap and snd on a list, as updated above, which gave me this error:

error:
    • No instance for (Functor Rose) arising from a use of ‘fmap’
    • In the expression: fmap snd bs'
      In the expression: let bs' = minimax' (MkRose b bs) in fmap snd bs'
      In an equation for ‘minimax’:
          minimax P1 (MkRose b bs)
            = let bs' = minimax' (MkRose b bs) in fmap snd bs'
    |
259 |     in  fmap snd bs'

How can I accomplish this in Haskell? Alternatively I can just write a function, if that's easier.

CodePudding user response：

You don't need fmap:

rmap :: (a -> b) -> Rose a -> Rose b
rmap f (MkRose a as) = MkRose (f a) (map (rmap f) as)

But having

instance Functor Rose where fmap = rmap

allows you to do neat things like (<$), and you don't have to keep remembering map, rmap, vmap, etc.

(Also, with {-# LANGUAGE DeriveFunctor #-}, you can simply write data Rose a = MkRose a [a] deriving Functor, and the instance is calculated for you.)

CodePudding user response：

Just add Functor to the deriving list:

data Rose a = MkRose a [Rose a]
    deriving (Eq, Show, Functor)

You might have to enable an extension DeriveFunctor.

Then you can just use fmap snd.

It will convert Rose (a,b) to Rose b for any types a and b. In particular, for (Board, Int) it will convert Rose (Board, Int) to Rose Int, by simply stripping away the first component of the tuple in each value position in the tree.

fmap     :: Functor f =>            (a -> b) -> f a -> f b
fmap snd :: Functor f =>                   f (a, b) -> f b
fmap @ Rose ::                   (a -> b) -> Rose a -> Rose b
fmap @ Rose @ (Board, Int) snd :: Rose (Board, Int) -> Rose Int

This uses TypeApplications but you don't need that, the types will be automatically selected according to the data you will supply, i.e. the variable you will apply fmap snd to. For example:

Prelude> t1 = MkRose (0,3) [MkRose (0,9) []]
Prelude> fmap snd t1
MkRose 3 [MkRose 9 []]
Prelude>

What you wrote in the comment is invalid syntax

bs' = MkRose (Board, Int) 
          [MkRose (Board,Int) [], MkRose (Board,Int) [] ]

if you have this as code, verbatim.

You can't do that. Board is a name of a type. Int is a name of a type. But a variable bs' is supposed to refer to a piece of data. If that datum is of type Rose (Bord, Int), it means that in each place where the type variable a appears, in the data type definition,

data Rose a = MkRose a [Rose a]
--                   ^       ^

there supposed to appear a piece of data of type (Board, Int) -- not simply type names. And that is a tuple holding two actual values, one of type Board, the other of type Int. For example, with Rose (String, Int):

t2 :: Rose (String, Int)
t2 = MkRose ("a", 1) [MkRose ("b", 2) [], MkRose ("c", 3) []]

fmap snd t2 
=> MkRose 1 [MkRose 2 [], MkRose 3 []]