时间戳

首页 > 解决方案 > 在 Haskell 中连接两个通用的 Either

haskell - 在 Haskell 中连接两个通用的 Either

问题描述

我正在寻找一种将两者Either a b结合Either c d在一起的方法，Either a (Either b (Either c d))作为最终结果。但它也应该能够递归地“平坦”两个要么，以防 if b ~ Eitheror/and d ~ Either。

我试图用fundep定义类型类：

class Adjoin a b c | a b -> c where
  adjoin :: a -> b -> c

但是无法为该类提出任何有意义的实例。我觉得可以通过类型族来实现，但我不够熟练。

本质上，我正在尝试从 Scala复制无形的Coproduct

标签： haskell

解决方案

我写了另一个答案，但它不正确，因为它没有递归地展平嵌套Either的 s。希望这个应该工作。

一些必需的扩展：

{-# LANGUAGE DataKinds, MultiParamTypeClasses, FunctionalDependencies, 
             UndecidableInstances, FlexibleInstances, ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}    -- To enable supplying types with @ 
{-# LANGUAGE AllowAmbiguousTypes #-} -- Not strictly necessary, just to avoid Proxy

和班级本身：

class Flatten input result | input -> result where
    flatten :: input -> result

-- Branch can be used as a kind thanks to DataKinds
data Branch = RebalanceNeeded
            | RebalanceNotNeeded
            | Atomic

type family WhichBranch t :: Branch where
     WhichBranch (Either (Either _ _) _) = RebalanceNeeded
     WhichBranch (Either _ _)            = RebalanceNotNeeded
     WhichBranch _                       = Atomic

class Flatten' (branch :: Branch) input result | branch input -> result where
    flatten' :: input -> result

-- We always delegate on the auxiliary class 
instance Flatten' (WhichBranch input) input result => Flatten input result where
    flatten = flatten' @(WhichBranch input)

-- The left branch is itself another either. We need to rebalance and keep flattening.
instance Flatten (Either x (Either y z)) r 
  => Flatten' RebalanceNeeded (Either (Either x y) z) r where
  flatten' e = case e of
      Left (Left x)  -> flatten @(Either x (Either y z)) (Left x)
      Left (Right y) -> flatten @(Either x (Either y z)) (Right (Left  y))
      Right z        -> flatten @(Either x (Either y z)) (Right (Right z))

-- The left branch is not itself an either. We only flatten the right branch.
instance (Flatten y y') => Flatten' RebalanceNotNeeded (Either x y) (Either x y') where
  flatten' e = case e of
      Left x  -> Left x
      Right y -> Right (flatten @y y)

instance Flatten' Atomic x x where
  flatten' = id

该解决方案使用WhichBranch类型族来检查最左边的类型。Flatten'结果被输入到一个使用额外信息的辅助类型类中。这是一种避免烦人的“重叠实例”错误的解决方法。

另一种选择是简单地在实例上放置{-# OVERLAPPABLE #-}和{-# OVERLAPPING #-}编译指示并在没有辅助类和类型族的情况下工作。

使用示例：

ghci> :t flatten (undefined :: Either (Either Bool Float) (Either (Either Char Word) Int))
Either Bool (Either Float (Either Char (Either Word Int)))

编辑：代替多参数类型类，编码这些单向转换的另一种方法是使用关联的类型族：

class Flatten input where
  type Flattened input -- associated type family that "computes" the flattened type
  flatten :: input -> Flattened input

class Flatten' (branch :: Branch) input where
  type Flattened' branch input 
  flatten' :: input -> Flattened' branch input

instance Flatten' (WhichBranch input) input => Flatten input where
    type Flattened input = Flattened' (WhichBranch input) input
    flatten = flatten' @(WhichBranch input)

instance Flatten                  (Either x (Either y z)) 
  => Flatten' RebalanceNeeded     (Either (Either x y) z) where
  type Flattened' RebalanceNeeded (Either (Either x y) z) 
     = Flattened                  (Either x (Either y z))
  flatten' e = flatten (case e of
      Left (Left x)  -> Left x
      Left (Right y) -> Right (Left  y)
      Right z        -> Right (Right z) 
                                :: Either x (Either y z))

instance Flatten y => Flatten' RebalanceNotNeeded (Either x y) where
  type Flattened' RebalanceNotNeeded (Either x y) = Either x (Flattened y)
  flatten' = fmap flatten

instance Flatten' Atomic x where
  type Flattened' Atomic x = x
  flatten' = id

优点是现在我们可以明确要求计算结果类型：

ghci> :kind! (Flattened (Either (Either Bool Float) (Either (Either Char Word) Int)))
Either Bool (Either Float (Either Char (Either Word Int)))

推荐阅读