Getting the head and tail of a custom List type Haskell -

i have custom list type follow:

data nnlist = sing | append ( nnlist a) ( nnlist a) deriving (eq) data clist = nil | notnil ( nnlist a) deriving (eq) 

and i'm trying implement function return head , tail of list.

clistget :: clist -> maybe (a, clist a)

my attempt:

clistget :: clist -> maybe (a, clist a) clistget nil             = nothing clistget xs@(notnil nxs) = case nxs of   sing x        -> (x, nil)   append l r    -> ((fst $ clistget (notnil l)), (append (snd $ clistget (notnil l)), r)) 

which me means keep going leftwards until single. once single element(head), return element , nil list. nil list combined list before return final result.

i'm not sure of logic 100% correct.

well, people refer data structure have kind of tree, not list. anyway...

problem #1: haskell indentation sensitive, , case expression not indented. leads parse error.

problem #2, , bigger one: haven't understood how maybe type works yet. impression think works nulls in more common languages, , throwing off.

in language like, say, java, null value can occur other value can. if have method following signature:

public foo makeafoo(bar somebar) 

...then legal call either of these ways:

// way #1: pass in actual value bar thebar = getmeabar(); foo result = makeafoo(thebar);  // way #2: pass in null foo result2 = makeafoo(null) 

thebar , null "parallel" in sense, or said more precisely, they have same type—you can replace 1 other in program , compile in both cases.

in haskell, on other hand, string "hello" , nothing not have same type, , cannot use 1 other goes. haskell distinguishes between these 3 things:

1. a string that's required there: "hello" :: string
2. the absence of optional string: nothing :: maybe string
3. the presence of optional string: just "hello" :: maybe string

the difference between #1 , #3 you're systematically missing in function. maybe a, in cases have value must use just, acts wrapper signify "this isn't a, it's maybe a."

first place you're missing just right hand sides of case expressions, can fix this:

-- still fails compile! clistget :: clist -> maybe (a, clist a) clistget nil             = nothing clistget xs@(notnil nxs) =     case nxs of                        -- added 'just' here , in next line:       sing x        -> (x, nil)       append l r    -> (fst $ clistget (notnil l), (append (snd $ clistget (notnil l)), r)) 

but isn't end of it, because you're doing fst $ clistget (notnil l), suffers converse problem: clistget returns maybe (a, clist a), fst works on (a, b), not on maybe (a, b). need pattern match on result of clistget test whether it's nothing or just (x, l'). (this same problem occurs in snd $ clistget (notnil l).)

third, you're using append constructor wrong. have in form of (append foo, bar), should have no comma between foo , bar. in haskell sort of thing give more confusing error messages other languages, because when haskell sees this, doesn't tell "you made syntax error"; haskell rather more literal languages, figures you're trying make pair append foo first element, , bar second one, concludes (append foo, bar) must have type (nnlist -> nnlist a, nnlist a).

the fourth , final problem: problem you've set not stated, , has no answer. want find "head" , "tail" of clist a. mean? in case of haskell [a] type, constructors [] , :, clear: head x in x:xs, , tail xs.

as understand you, mean "head" seems leftmost element of recursive structure. way:

clisthead :: clist -> maybe clisthead nil = nothing -- no need cram 1 definition; deal -- nnlist case in auxiliary function, it's easier... clistget (notnil nxs) = (nnlisthead nxs)  -- note how easier function write, because since 'nnlist' -- doesn't have 'nil' case, there's no need mess around 'maybe' -- here.  basically, splitting problem 2 functions, -- 'clisthead' needs care 'maybe' , 'just'. nnlisthead :: nnlist -> nnlisthead (sing a) = nnlisthead (append l _) = nnlisthead l 

so might think "the tail" else. well, problem "everything else" not subpart of clist or nnlist. take example:

example :: clist int example = notnil (append (append (sing 1) (sing 2)) (sing 3)) 

the "head" 1. there no subpart of structure defined in example contains 2 , 3 without containing 1 well. you'd have construct new clist different shape original that. that's possible do, don't see value of beginner's exercise, frankly.

in case it's not clear mean "subpart," think of example tree:

        notnil           |           v         append          / \         v   v      sing   append       |      / \       v     v   v       1  sing   sing           |      |           v      v           2      3 

subpart = subtree.