How to have a type with indexable but optional elements requiring one to exist in Haskell

I need a type structure that has a certain number of "slots" that are indexable (so we can react to items in slot 1 or 2 or 3 separately and consistently)

(Maybe a, Maybe b, Maybe c...) is unwieldy, difficult for a framework to do much with, and allows r开发者_StackOverflowepresentation of (Nothing, Nothing...) which should not be allowed for what I'm doing.

This works: data Or a b = OrBoth a b | OrLeft a | OrRight b

and has exactly the correct semantics, but it's a mess to pattern match on.

OrBoth tas1 (OrRight (OrRight new)) ->
OrBoth tas1 (OrRight (OrBoth _ new)) ->
OrBoth tas1 (OrBoth _ (OrRight new)) ->
OrBoth tas1 (OrBoth _ (OrBoth _ new)) ->

Any other ideas of how this might be done efficiently and readably?

Ed'ka's answer is great and I have another question for it:

Is it possible to have it create the right sized "tuple"?

step :: (Nothingable a, Nothingable b) => SignalFunction a b -> a -> (SignalFunction a b, b)
step sf nothing = (sf, nothing) -- second nothing here is error
step sf a = transition sf a

src/Processors.hs:59:23:
    Couldn't match expected type `b' against inferred type `a'
      `b' is a rigid type variable bound by
          the type signature for `step' at src/Processors.hs:58:36
      `a' is a rigid type variable bound by
          the type signature for `step' at src/Processors.hs:58:21
    In the expression: nothing

GADT-s can be handy for this type of things. Not sure how practical this is, but you can pattern match and it won't allow you to pass an "empty" (all 'None') case. Being "heterogeneous collection" Spec can be of arbitrary length and can specify elements of different types (tuple-like).

{-# LANGUAGE TypeOperators, EmptyDataDecls, GADTs, TypeFamilies #-}

data Empty
data NonEmpty

-- Infix forms of data type and constructor (looks nicer here)
infixr 7 :*:
data a :*: b

-- GADT definition of heterogeneous list
-- with 'e' parameter specifing possible "emptiness" of the result (if all items in the list are 'None')
data Spec a e where
    (:*:) :: Spec a e1 -> Spec b e2 -> Spec (a :*: b) (Calc e1 e2)
    None :: Spec a Empty
    Some :: a -> Spec a NonEmpty


-- Only when two 'Empty' Specs are cons-ed will we get Empty 
type family Calc a b
type instance Calc Empty Empty = Empty 
type instance Calc Empty NonEmpty = NonEmpty 
type instance Calc NonEmpty Empty = NonEmpty 
type instance Calc NonEmpty NonEmpty = NonEmpty 


-- Example of usage
-- We need to specify the type here (GADT..) and not to forget to add 'NonEmpty'
foo :: Spec (Int :*: Bool :*: Char) NonEmpty -> Int 
foo (Some 5 :*: Some _ :*: Some _) = 1 
foo (Some _ :*: Some b :*: Some 'c') = if b then 2 else 22 
foo (Some 4 :*: None :*: None) = 3
foo (None :*: Some _ :*: None) = 4
foo (None :*: None :*: Some 'a') = 5
foo (Some _ :*: Some _ :*: Some _) = 42

-- Some test cases:
t1 = foo (Some 5 :*: Some True :*: Some 'a')    -- ==> 1
t2 = foo (Some 8 :*: Some False :*: Some 'c')   -- ==> 22
t3 = foo (Some 4 :*: None  :*: None)            -- ==> 3
t4 = foo (None :*: Some True :*: None)          -- ==> 4
t5 = foo (None :*: Some False :*: None)         -- ==> 4
t6 = foo (Some 1 :*: Some True :*: Some 'e')    -- ==> 42
-- t7 = foo (None :*: None :*: None)    -- Will not compile due to Empty/NonEmpty mismatch (at least one item should be not 'None')

PS Also: http://homepages.cwi.nl/~ralf/HList/ "Strongly typed heterogeneous collections"

UPDATE: Following the author's comments: If we omit the requirement of the static check against "all Nothing's" case and subsequently get rid of GADT's (which indeed require explicit type specification whenever used) we can use standard ADT plus some simple type-level calculations to produce "all Nothing's" case for dynamic check:

{-# LANGUAGE TypeOperators, FlexibleInstances #-}

infixr 7 :*:
data a :*: b = a :*: b

-- type-level manipulations against our "custom-made tuple"
-- for now it only generates a tuple with all members set to Nothing, but can be extended
class Nothingable a where
    nothing :: a

instance Nothingable (Maybe a) where
    nothing = Nothing
instance (Nothingable b) => Nothingable (Maybe a :*: b) where
    nothing = Nothing :*: nothing

-- the same tests
foo (Just 5 :*: Just True :*: Just 'a') = 1
foo (Just _ :*: Just b :*: Just 'c') = if b then 2 else 22 
foo (Just 4 :*: Nothing :*: Nothing) = 3
foo (Nothing :*: Just _ :*: Nothing) = 4
foo (Nothing :*: Nothing :*: Just 'a') = 5
foo (Just _ :*: Just _ :*: Just _) = 42
-- test  for "all Nothing"
foo nothing = error "Need at least one non 'Nothing' case"

-- works for let and case bindings
boo t = 
    let (Just a :*: b) = t
    in case b of
         (Just _ :*: Nothing :*: Just c) -> c
         nothing                         -> 0

t1 = foo (Just 5 :*: Just True :*: Just 'a')   -- ==> 1
t2 = foo (Just 8 :*: Just False :*: Just 'c')  -- ==> 22
t3 = foo (Just 4 :*: Nothing :*: Nothing)      -- ==> 3
t4 = foo (Nothing :*: Just True :*: Nothing)   -- ==> 4
t5 = foo (Nothing :*: Just False :*: Nothing)  -- ==> 4
t6 = foo (Just 1 :*: Just True :*: Just 'e')   -- ==> 42
t7 = foo (Nothing :*: Nothing :*: Nothing)     -- ==> error

t8 = boo (Just undefined :*: Just True :*: Nothing :*: Just 5)   -- ==> 5
t9 = boo (Just undefined :*: Just True :*: Nothing :*: Nothing)  -- ==> 0 

2ND UPDATE: Please disregard my previous "Update": it is wrong. Of course you cannot match against function nothing - only data contructor or variable is allowed here, so nothing is considered being variable (like in your example: someFun nothing = nothing is equivalent to someFun a = a). It still can be useful though as a "all Nothing" tuple generator and, if we add "test" function isNothing to our class:

class Nothingable a where
    nothing :: a
    isNothing :: a -> Bool

instance Nothingable (Maybe a) where
    nothing = Nothing
    isNothing Nothing = True
    isNothing _ = False

instance (Nothingable b) => Nothingable (Maybe a :*: b) where
    nothing = Nothing :*: nothing
    isNothing (Nothing :*: a) = isNothing a
    isNothing _ = False

we then will be able to use either Haskel98 guards:

koo (Just 5 :*: Just "42" :*: Just True) = (Just True :*: Just 5.0 :*: Nothing)
koo ns | isNothing ns = nothing  -- 'nothing' here generates a tuple of three members all set to Nothing

or fancy view patterns (with "ViewPatterns" GHC extension):

koo (Just 5 :*: Just "42" :*: Just True) = (Just True :*: Just 5.0 :*: Nothing)
koo (Just 5 :*: (isNothing -> True)) = (Just True :*: Nothing :*: nothing)

and:

boo t = 
    let (Just a :*: b) = t
    in case b of
         (Just _ :*: Nothing :*: Just c) -> c
         (isNothing -> True)             -> 0
         _                               -> error "failed"

Shame on me for the previous Update - it was working simply because I put nothing match as a last case in function definitions (it was matching any argument not picked up by the previous cases - binding it to that misleading nothing variable). Sorry, for that!

Personally, I'd use Either (a,b) (Either a b). But that's not any cleaner for pattern matching.

What you really want to use are projection functions and pattern guards.

getLeft :: Or a b -> Maybe a
foo x
  | Just a <- getLeft x, Just b <- getRight x = ...
  | Just a <- getLeft x = ...

Edit: I just realized another approach -- write the eliminator/catamorphism over your type.

import Data.Monoid

data Or a b = OrBoth a b | OrLeft a | OrRight b

orElim :: (t -> t2) -> (t1 -> t2) -> (t -> t1 -> t2) -> Or t t1 -> t2
orElim onLeft onRight onBoth x =
    case x of
      OrLeft  a  -> onLeft  a
      OrRight b  -> onRight b
      OrBoth a b -> onBoth  a b

morElim :: (Monoid a) => (t -> a) -> (t1 -> a) -> Or t t1 -> a
morElim onLeft onRight x =
    case x of
      OrLeft  a  -> onLeft  a
      OrRight b  -> onRight b
      OrBoth a b -> onLeft a `mappend` onRight b

Why are your elements of OrBoth of type Or? If you know the second field is going to be another Or then just flatten the structure OrBoth x (Or a b) becomes OrBothA x a | OrBothB x b.

I was also going to suggest viewpatterns, but I see sclv coverd that!

This will work as a solution only if you want your Or a b data structures to be able to contain a finite and manageable number of data types.

In this case you may do something like

data OrValue = OrInt Int | OrChar Char | OrString String | OrBool Bool

and then you may simply deal with [OrValue] rather than unwrapping a bunch of data constructors.

Note that this does allow the possibility of a completely null input -- the empty list -- but it is fairly easy to check against.

For an example of how this technique is used in actual applications, you may take a look at the Text.JSON library (which you may get from cabal via cabal install json) -- in particular its JSValue data type.

Playing around a bit, here's what I came up with.

data Or a b = Or { extractLeft :: Maybe a, extractRight :: Maybe b }
            deriving (Show, Eq)

Some methods, other than the extractLeft and extractRight from record syntax...

-- only works for "Or" with same type in left and right!
orExtract :: Or a a -> Maybe a
orExtract (Or (Just x) Nothing) = Just x
orExtract (Or Nothing (Just y)) = Just y
orExtract _ = Nothing

orLeft :: a -> Or a b
orLeft x = Or (Just x) Nothing

lEmpty (Or Nothing _) = True
lEmpty _ = False

orRight :: b -> Or a b
orRight x = Or Nothing (Just x)

rEmpty (Or _ Nothing) = True
rEmpty _ = False
rEmpty' x = case extractRight x of Nothing -> True
                           _ -> False


orBoth :: a -> b -> Or a b
orBoth x y = Or (Just x) (Just y)

Some data built with this type (using smart constructors)

foo :: Or Int Char
foo = orBoth 1 's'
bar :: Or Int a
bar = orLeft 3
baz :: Or a Char
baz = orRight 'f'

A method that uses guards (not pattern matching...)

orMethod orObj
    | lEmpty orObj = undefined
    | rEmpty orObj = undefined
    | lEmpty lObj  = undefined
    | rEmpty rObj = undefined
        where (Just lObj) = extractLeft orObj
              (Just rObj) = extractRight orObj

I'm not sure that using this sort of thing is a good idea, though.I agree with drvitek's approach more; you will be using a finite number of types, and so your data structures can be generalized into the same "type", at which point you can use list operations and patterns.

I'd caution against using the Or type directly, in my opinion its just too general to be pleasant to program with.

Basically Or is a Sum-and-Product datatype - sum is Either in Haskell, and product is (,). With sum and product - plus the null constructor () - you can model Haskell's algebraic types. This is the model for some Generics libraries and its also the model for some serialization formats such as ASDL (the "Abstract Syntax Description Language"). The sum and product view really is general...

But because it is so general it is cumbersome to use - you really want to get out of the sum-and-product view as quickly as possible and use a more direct syntax that matches the data you want to work with. Another downside to Or is that it would generate very long type signatures when you have nesting. It will also be difficult to write functions to traverse nested Or structures in a typed language.