data-structures - 有没有办法在 Haskell 中做更多的 "dynamic"数据构造函数？

是否有一些 Haskell 扩展可以创建比 GADT 更复杂的数据构造函数？

假设我想创建一个有序列表的数据结构，并有一个类似于 (:) 的数据构造函数，用于处理列表，具有类型签名:

data MyOrdList a where
    (>>>) :: (Ord a) -> a -> MyOrdList a -> MyOrdList a

但我希望 (>>>) 具有特定的行为，如下所示:

(>>>) :: (Ord a) => a -> [a] -> [a]
x >>> [] = [x]
x >>> xs = low ++ [x] ++ high
  where low  = filter (<x) xs
      high = filter (>x) xs

所以结构将始终是有序结构。 (我现在不知道这是不是一个好的做法，我只是提供了我想要的行为类型的最简单的例子)。

当然，我可以使用函数 (>>>) ，但是我将没有模式匹配和其他好处，我希望 >>> 是一个数据构造函数。

有没有办法做这样的事情？

最佳答案

您可以使 :>>> 成为数据构造函数，但您必须隐藏它以保持不变。请注意，您可以像在 render 中那样对其进行模式匹配:

module MyOrdList (mkMyOrdList,MyOrdList,render) where

import Data.List

import qualified Data.ByteString as BS

data MyOrdList a
  = EmptyDataList
  | (:>>>) a (MyOrdList a)
  deriving (Show)

mkMyOrdList [] = EmptyDataList
mkMyOrdList xs = y :>>> mkMyOrdList ys
  where y = minimum xs
        ys = delete y xs

render :: (Show a) => MyOrdList a -> String
render EmptyDataList = "<empty>"
render (x :>>> xs) = (show x) ++ " -> " ++ render xs

然后你可以像这样使用 MyOrdList 模块

module Main where

import Control.Applicative
import System.IO

import qualified Data.ByteString as BS

import MyOrdList

main = do
  h <- openBinaryFile "/dev/urandom" ReadMode
  cs <- readBytes 10 h
  -- but you cannot write...
  -- let bad = 3 :>>> 2 :>>> 1 :>>> EmptyOrdList
  putStrLn (render $ mkMyOrdList cs)
  where
    readBytes 0 _ = return []
    readBytes n h = do c <- BS.head <$> BS.hGet h 1
                       cs <- readBytes (n-1) h
                       return (c:cs)

示例输出:

54 -> 57 -> 64 -> 98 -> 131 -> 146 -> 147 -> 148 -> 190 -> 250 ->