Geek asks and answers

Getting the header and tail of a custom list type in Haskell

I have my own list type:

data NNList a = Sing a | Append ( NNList a) ( NNList a) deriving (Eq)
data CList a = Nil | NotNil ( NNList a) deriving (Eq)

I am trying to implement a function that returns the head and tail of a list:

cListGet :: CList a → Possible (a, CList a)

My attempt:

cListGet :: CList a -> 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))

What does it mean to me to keep going left until I get a single. As soon as I get a single element (head), return the element and list Nil. This Nil list is then combined with the list before returning it as the final result.

I'm not even sure if the logic is 100% correct.

+5
source share
4 answers

Well, people usually refer to the data structure that you have as a kind of tree, not a list. But anyway...

№ 1: Haskell , case . .

№2, : , Maybe. , , nulls , .

, , Java, null - , , . :

public Foo makeAFoo(Bar someBar)

... :

// Way #1: pass in an actual value
Bar theBar = getMeABar();
Foo result = makeAFoo(theBar);

// Way #2: pass in a null
Foo result2 = makeAFoo(null)

theBar null "" , , : , .

Haskell, , "hello" Nothing , , . :

  • , : "hello" :: String
  • : Nothing :: Maybe String
  • : Just "hello" :: Maybe String

# 1 # 3 - , . Maybe a, , , Just, " a, a Maybe a."

, Just - case, :

-- This still fails to compile!
cListGet :: CList a -> Maybe (a, CList a)
cListGet Nil             = Nothing
cListGet xs@(NotNil nxs) =
    case nxs of
                       -- I added 'Just' here and in the next line:
      Sing x        -> Just (x, Nil)
      Append l r    -> Just (fst $ cListGet (NotNil l), (Append (snd $ cListGet (NotNil l)), r))

, fst $ cListGet (NotNil l), : cListGet Maybe (a, CList a), fst (a, b), Maybe (a, b). cListGet, , Nothing Just (x, l'). ( snd $ cListGet (NotNil l).)

-, Append. (Append foo, bar), foo bar. Haskell , , , Haskell , " "; Haskell , , Append foo , bar - , , (Append foo, bar) (NNList a -> NNList a, NNList a) > .

: , , , , . , "" "" CList a. ? Haskell [a] [] : : - x x:xs, - xs.

, , "", , . :

cListHead :: CList a -> Maybe a
cListHead Nil = Nothing
-- No need to cram everything together into one definition; deal with
-- the NNList case in an auxiliary function, it easier...
cListGet (NotNil nxs) = Just (nnListHead nxs)

-- Note how much easier this function is to write, because since 'NNList'
-- doesn't have a 'Nil' case, there no need to mess around with 'Maybe'
-- here.  Basically, by splitting the problem into two functions, only
-- 'cListHead' needs to care about 'Maybe' and 'Just'.
nnListHead :: NNList a -> a
nnListHead (Sing a) = a
nnListHead (Append l _) = nnListHead l

, , "" - . , " " CList NNList. :

example :: CList Int
example = NotNil (Append (Append (Sing 1) (Sing 2)) (Sing 3))

"" 1. , example, 2 3 1. CList , , . , , .

, "", :

        NotNil
          |
          v
        Append
         / \
        v   v
     Sing   Append
      |      / \
      v     v   v
      1  Sing   Sing
          |      |
          v      v
          2      3

= .

+13

: , , (==).

Edit:

-, , . ; (Google - ).

, : nnListGet :: NNList a -> (a, CList a), cListGet.

+3

( ) : , . , , . Foldable. :

import Prelude hiding (foldr)
import Data.Foldable

data NNList a = Sing a | Append (NNList a) (NNList a) deriving (Eq)
data CList a = Nil | NotNil (NNList a) deriving (Eq)

instance Foldable NNList where
    foldr f z (Sing x)          = f x z
    foldr f z (Append xs ys)    = foldr f (foldr f z ys) xs
instance Foldable CList where
    foldr _ z Nil               = z
    foldr f z (NotNil xs)       = foldr f z xs

, Data.Foldable , /, ..

Foldable headMaybe, , First monoid. monoid, . , Foldable , :

import Data.Monoid

headMaybe :: (Foldable f) => f a -> Maybe a
headMaybe = getFirst . foldMap (First . Just)

( foldr, Maybe Alternative, :

import Control.Applicative

headMaybe = foldr (\x y -> pure x <|> y) Nothing

.)

- tailMaybe. , headMaybe, . .

. :

+1
source

Why did you declare this in two types? Here's a more appropriate type declaration with the right function:

data CList a
  = Nil
  | Sing a
  | Append (CList a) (CList a)
  deriving (Eq)

headAndTail :: CList a -> Maybe (a, CList a)
headAndTail Nil = Nothing
headAndTail (Sing a) = Just (a, Nil)
headAndTail (Append a b) = 
  case headAndTail a of
    Nothing -> headAndTail b
    Just (head, tail) -> Just (head, Append tail b)
0
source

More articles:


All Articles