CutList: Lists with Prolog-like Cut!

Cut.hs

{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE TypeFamilies #-}

module Cut where

import Control.Monad
import GHC.Exts

data CutList a
    = Cons a (CutList a)
    | Nil
    | Cut

instance IsList (CutList a) where
    type Item (CutList a) = a

    fromList (x:xs) = Cons x (fromList xs)
    fromList []     = Nil

    toList (Cons x xs) = x : toList xs
    toList _           = []

cut :: CutList a
cut = Cut

instance Functor CutList where
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)
    fmap f Nil         = Nil
    fmap f Cut         = Cut

instance Applicative CutList where
    pure x = Cons x Nil

    (<*>) = ap

append :: CutList a -> CutList a -> CutList a
append (Cons x xs) ys = Cons x (append xs ys)
append Nil ys         = ys
append Cut ys         = Nil

instance Monad CutList where
    Cons x xs >>= f = append (f x) (xs >>= f)
    Nil       >>= f = Nil
    Cut       >>= f = Cut