Есть ли способ сделать больше «динамических» конструкторов данных в 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

Вы можете сделать 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 и (>>>), но у вас все еще есть удобство сопоставления с образцом.

Answer 2

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