Existe-t-il un moyen de faire plus de constructeurs de données "dynamiques" dans Haskell?

Question

Existe-t-il une extension Haskell permettant la création de constructeurs de données plus complexes que GADT?

Supposons que je voulais créer une structure de données est une liste ordonnée, et un constructeur de données similaire à (:) qui travaillent avec des listes, avec la signature de type:

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

Mais je veux (>>>) d'avoir un spécifique comportement, quelque chose comme ceci:

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

Ainsi, la structure sera toujours une structure ordonnée. (Je ne sais pas si c'est une bonne pratique, je propose juste l'exemple le plus simple qui m'est arrivé du type de comportement que je veux).

Bien sûr, je peux utiliser une fonction (>>>), mais alors je n'aurai pas de correspondance de modèle et d'autres avantages que je l'aurais >>> était un constructeur de données.

Est-il possible de faire quelque chose comme ça?

Answer 1

Vous pouvez faire :>>> un constructeur de données, mais vous devez le cacher pour préserver votre invariant. Notez que vous pouvez modèle match contre elle, comme dans 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 

Ensuite, vous pouvez utiliser le module MyOrdList comme dans

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) 

Exemple de sortie:

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

Answer 2

Vous pourriez faire MyOrdList un type abstrait et (>>>) une fonction et utiliser des modèles de vue. Pour simplifier, j'utilise une liste standard en tant que «backend» ici.

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) 

Vous pouvez l'utiliser comme ça:

{-# LANGUAGE ViewPatterns #-} 

import MyOrdList 

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

Travaux:

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

donc votre type est abstraite, les listes ne peuvent être construits par emptyOrdList et (>>>), mais vous avez encore un peu commodité de correspondance de motif.