How to lift a fold|map|both into the Either monad?

Question

A "map" of type

mapIsh :: Traversable t => (a -> Either b c) -> t a -> Either b (t c)

would be a start. (Hayoo doesn't find one.) Or a "fold" of type

foldIsh :: (b -> a -> Either l b) -> b -> t a -> Either l b

Best of all (for my case) would be this:

mapAccumIsh :: (a -> b -> Either l (a, c)) -> a -> t b -> Either l (a, t c)

That might be all you need to read. In case you want more details, though, here's a concrete example:

Imagine a treelike structure to mapAccum over. Each branch, after evaluating its children, gets transformed by some function of its children and the accumulator.

Here's some working code that adds each Tree's value to the accumulator, and also adds to each Branch's label the product of its childrens' labels:

module Temp where

import Data.List

data Tree = Leaf Float | Branch Float [Tree] deriving (Show)

label :: Tree -> Float
label (Leaf i) = i
label (Branch i _) = i

f :: Float -> Tree -> (Float, Tree)
f i (Leaf j) = (i+j, Leaf j)
f i (Branch j ts) = (i + tf, Branch tf ts2) where
  (i2, ts2) = mapAccumL f i ts
  tf = j + (foldl (*) 1 $ map label ts2)

-- the problem: what if instead of (*) in the line above, we used this?
evenMult :: Float -> Float -> Either String Float
evenMult a b = case even $ round b of True -> Right $ a * b
                                      False -> Left "that's odd" 

go = f 0 $ Branch 2 [Branch 2 [Leaf 2]
                    ,Branch 2 [Leaf 2, Leaf (-2)]]

Here's what that returns:

(-6.0,Branch (-6.0) [Branch 4.0 [Leaf 2.0]
                    ,Branch (-2.0) [Leaf 2.0,Leaf (-2.0)]])

But what if, instead of using (*) in the foldl, we used evenMult?