Есть ли способ сделать больше «динамических» конструкторов данных в Haskell?

Question

Есть ли расширение 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 

Таким образом, структура будет всегда упорядоченной структурой. (Я не сейчас, если это хорошая практика, я просто предлагаю самый простой пример, который вызвал меня по типу поведения, которое я хочу).

Конечно, я могу использовать функцию (>>>), но тогда у меня не будет соответствия шаблону и других преимуществ, которые у меня были бы у него. >>> был конструктором данных.

Есть ли способ сделать что-то подобное?

Answer 1

Вы можете сделать конструктор данных :>>>, но вам нужно скрыть его, чтобы сохранить ваш инвариант. Обратите внимание на то, что вы можете шаблон матча против него, как в 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 -> <empty>

Answer 2

Вы могли бы сделать MyOrdList абстрактный тип и (>>>) функции и использование шаблонов. Для простоты я использую стандартный список как «бэкэнд» здесь.

module MyOrdList 
    (MyOrdList, 
    MyOrdListView (OrdNil, OrdCons), 
    (>>>), 
    emptyOrdList, 
    ordview 
) where 

import Data.List (sort) 

newtype MyOrdList a = List [a] 
    deriving Show 

data MyOrdListView a = OrdNil | OrdCons a (MyOrdList a) 

infixr 5 >>> 

(>>>) :: (Ord a) => a -> MyOrdList a -> MyOrdList a 
x >>> (List xs) = List (sort $ x:xs) 

emptyOrdList = List [] 

ordview :: MyOrdList a -> MyOrdListView a 
ordview (List []) = OrdNil 
ordview (List (x:xs)) = OrdCons x (List xs) 

Вы можете использовать его так:

{-# LANGUAGE ViewPatterns #-} 

import MyOrdList 

ordlength :: MyOrdList a -> Int 
ordlength (ordview -> OrdNil) = 0 
ordlength (ordview -> OrdCons x xs) = 1 + ordlength xs 

Работы:

*Main> ordlength $ 2 >>> 3 >>> 1 >>> emptyOrdList 
3 
*Main> 2 >>> 3 >>> 1 >>> emptyOrdList 
List [1,2,3] 

Так ваш тип является абстрактным, списки могут быть построены только emptyOrdList и (>>>), но вы все еще есть некоторые образец сопоставив удобный.