Haskell嵌套列表追加

我想寫一個函數，將一個給定的值附加到嵌套列表結構的最內層列表，但我遇到了類型錯誤，當我甚至不知道什麼是這樣的函數的類型簽名是。Haskell嵌套列表追加

digpend a xs = case xs of [_:_] -> map (digpend a) xs 
          [[]] -> [[a]] 
          xs -> a:xs

例如，

digpend 555 [ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ]

應該返回

[ [ [ 555,5,1,-12,33 ] , [ 555,6,22 ] ] , [ [ 555,-9,0,9,12,83 ] ] ]

理想情況下，它會通過遞歸嵌套的任何級別的工作。這是否允許？

來源

2013-06-28 Feryll

@AndrewC：我不能完全看還有多少，但它可以使用多參數類型類來管理，不是嗎？ '（digpend a）'想變成多態的事實不一定是個問題。 – PLL

這是一個不完全，圓滿執行，使用類型類：

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} 

class DigPend a b where 
    digpend :: a -> [b] -> [b] 

instance DigPend a a where 
    digpend x xs = (x:xs) 

instance (DigPend a b) => (DigPend a [b]) where 
    digpend x xs = map (digpend x) xs

它運作良好，只要參數的類型詳細說明如下：

*Main> digpend (5 :: Int) ([6,7,8] :: [Int]) 
[5,6,7,8] 
*Main> digpend (555 :: Int) ([[[5,1,-12,33],[6,22]],[[-9,0,9,12,83]]] :: [[[Int]]]) 
[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]] 
*Main> digpend (5 :: Int) ([] :: [Int]) 
[5] 
*Main> digpend (5 :: Int) ([] :: [[Int]]) 
[]

但是，像digpend 5 [6,7,8]這樣的調用會觸發大量「模糊類型變量」錯誤 - 類似於5的數字文字是多態的（它可以包含任何Num的實例），而ghci通常會愉快地默認爲Integer，它首先嚐試解決輸入DigPend的類別約束，並且在該階段沒有足夠的類型信息來知道要應用哪個實例digpend。

來源

2013-06-28 16:37:51 PLL

解決這個問題需要一些類型級別的編程技巧和一些GHC擴展。

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE OverlappingInstances #-} 

class Digpend a d where 
    digpend :: a -> d -> d 

instance (Digpend a d) => Digpend a [d] where 
    digpend a list = map (digpend a) list 

instance Digpend a [a] where 
    digpend a list = a : list 

main = do 
    -- We have to help the compiler disambiguate the numbers by putting explicit 
    -- type signatures: 
    print $ digpend 
    (555 :: Int) 
    ([ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ] :: [[[Int]]]) 
    -- In case of specific literals, such as `Char`, it's not a problem though. 
    print $ digpend '!' [['a', 'b', 'c'], "def"]

結果：

[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]] 
["!abc","!def"]

來源

2013-06-28 16:34:21

有趣的是，我們來到幾乎完全相同的解決方案！我想知道是否有任何方法不需要明確的消歧？ – PLL

@PLL歧義問題不是我們解決方案的問題，而是數字文字被推斷爲'Num a => a'的事實。由於我們的類是多態的，因此編譯器不能使用它們來消除歧義。在現實生活中，它不會成爲一個問題，因爲這個函數將被用在特定的上下文中，編譯器可以從中推斷出特定的類型。也有可能通過利用函數依賴來推斷基於另一個參數的參數。 –

歧義不僅來自數字文字，因爲通常ghc（i）會愉快地保持它們的多態性或爲它們選擇默認值;它是這種多態性與我們稍微棘手的靈活實例之間的某種相互作用。它也不一定會在實際使用中消失，因爲多態功能當然不會。功能依賴可能是嘗試改進事物的好方法，是的（雖然我們目前定義的類在任何方向都不起作用，所以它不直接適用於我們當前的方法）。 – PLL

如果你能/允許定義自己的數據類型，還可以使用以下命令：

data Tree a = Leaves [a] | InnerNodes [Tree a] deriving (Show) 

digpend :: a -> Tree a -> Tree a 
digpend x (Leaves xs) = Leaves $ x:xs 
digpend x (InnerNodes []) = InnerNodes [Leaves [x]] 
digpend x (InnerNodes xs) = InnerNodes . map (digpend x) $ xs

一些輸出的例子：

*Main> digpend 10 $ InnerNodes [ Leaves [], Leaves [], InnerNodes []] 
InnerNodes [Leaves [10],Leaves [10],InnerNodes [Leaves [10]]] 
*Main> digpend 555 $ InnerNodes [InnerNodes [Leaves [5, 1, -12, 33], Leaves [6, 22]], InnerNodes [Leaves [-9, 0, 9, 12, 83]]] 
InnerNodes [InnerNodes [Leaves [555,5,1,-12,33],Leaves [555,6,22]],InnerNodes [Leaves [555,-9,0,9,12,83]]]

來源

2013-06-28 17:27:05 Alexandros

Haskell嵌套列表追加

回答

相關問題