Haskell:为树中的每个级别关联多态函数

Question

美好的一天!

我有一个元素树:

data Tree a = Node [Tree a]
            | Leaf a

我需要到达那棵树的叶子.从根到叶的路径由一系列switch函数确定.该树中的每个层对应于一个特定的switch函数,该函数将某些内容作为参数并将索引返回到子树.

class Switchable a where
    getIndex :: a -> Int

data SwitchData = forall c. Switchable c => SwitchData c

最终目标是提供一个期望所有必需的函数SwitchData并返回树中的叶子.

但我认为无法在类型级别强制执行一对一映射.我当前的switch 函数实现接受一个SwitchData实例列表:

switch :: SwitchData -> Tree a -> Tree a
switch (SwitchData c) (Node vec) = vec `V.unsafeIndex` getIndex c
switch _ _ = error "switch: performing switch on a Leaf of context tree"

switchOnData :: [SwitchData] -> Tree a -> a
switchOnData (x:xs) tree = switchOnData xs $ switch x tree
switchOnData [] (Leaf c) = c
switchOnData [] (Node _) = error "switchOnData: partial data"

Switchable在编译时和运行时都不考虑实例的顺序和确切类型,对于程序员来说,这是正确的,这让我很烦恼.这个要点反映了当前的婚外情.

你能否提出一些方法来建立上下文树中各层与特定实例之间的一对一映射Switchable？

Answer 1

您当前的解决方案相当于简单switchOnIndices :: [Int] -> Tree a -> a(只需getIndex 在存储到列表中之前应用!).通过包含返回来明确"部分" Maybe这个,这实际上可能是理想的签名,简单而精细.

但显然,你的真实用例更复杂; 你希望每个级别都有基本不同的词典.然后,您实际上需要将多个类型的类型链接到树深度.你正在寻找一些疯狂的近乎依赖型的hackery!

{-# LANGUAGE GADTs, TypeOperators, LambdaCase #-}

infixr 5 :&

data Nil = Nil
data s :& ss where
  (:&) :: s -> ss -> s :& ss

data Tree switch a where
  Node ::
     (s -> Tree ss a)  -- Such a function is equiv. to `Switchable c => (c, [Tree a])`.
     -> Tree (s :& ss) a
  Leaf :: a -> Tree Nil a

switch :: s -> Tree (s :& ss) a -> Tree ss a
switch s (Node f) = f s

switchOnData :: s -> Tree s a -> a
switchOnData sw (Node f) = switchOnData ss $ f s
 where (s :& ss) = sw
switchOnData _ (Leaf a) = a

data Sign = P | M

signTree :: Tree (Sign :& Sign :& Nil) Char
signTree = Node $ \case P -> Node $ \case P -> Leaf 'a'
                                          M -> Leaf 'b'
                        M -> Node $ \case P -> Leaf 'c'
                                          M -> Leaf 'd'

testSwitch :: IO()
testSwitch = print $ switchOnData (P :& M :& Nil) signTree

main = testSwitch

当然,这极大地限制了树结构的灵活性:每个级别具有固定的预定数量的节点.事实上,这使整个结构例如signTree等同于简单(Sign, Sign) -> Char,所以除非你真的需要一个特定原因的树(例如附加到节点的额外信息),为什么不只是使用它!

或者,再次,更简单的[Int] -> Tree a -> a签名方式.但是使用存在感对我来说毫无意义.