5

カスタムリストタイプがあります：

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

リストの先頭と末尾を返す関数を実装しようとしています。

cListGet :: CList a->たぶん（a、CList a）

私の試み：

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))

私にとってこれは、私がシングルを手に入れるまで左に進み続けることを意味します。単一の要素（ヘッド）を取得したら、要素とNilリストを返します。このNilリストは、最終結果として返される前にリストと結合されます。

ロジックが100％正しいかどうかさえわかりません。

4

4 に答える 4

13

さて、人々は通常、あなたが持っているデータ構造をリストではなく一種のツリーと呼びます。とにかく...

問題＃1：Haskellはインデントに敏感であり、case式がインデントされていません。これにより、解析エラーが発生します。

問題＃2、そしてより大きな問題：あなたはタイプがどのように機能するかをまだ理解してMaybeいません。より一般的な言語ではnullのように機能すると思われる印象を受けますが、これはあなたを失望させています。

たとえば、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は同じタイプではなく、一方を他方の場所で使用することはできません。Haskellは、次の3つのことを区別しています。

  1. そこにある必要がある文字列："hello" :: String
  2. オプションの文字列がない：Nothing :: Maybe String
  3. オプションの文字列の存在：Just "hello" :: Maybe String

＃1と＃3の違いは、関数に体系的に欠けているものです。を使用するMaybe aと、値を使用する必要Justがあります。これは、「これは単なるではなく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)cListGetNothingJust (x, l')snd $ cListGet (NotNil l)

第三に、Appendコンストラクターを間違って使用しています。との間に(Append foo, bar)コンマを入れないでください。Haskellでは、この種のことは他のほとんどの言語よりも紛らわしいエラーメッセージを表示します。Haskellがこれを見ると、「構文エラーが発生した」とは表示されないためです。Haskellはほとんどの言語よりも文字通りであるため、最初の要素として、および2番目の要素としてペアを作成しようとしていると見なされるため、タイプがである必要があると結論付けられます。foobarAppend foobar(Append foo, bar)(NNList a -> NNList a, NNList a)

4番目の最後の問題：自分で設定した問題は明確に述べられていないため、良い答えはありません。の「頭」と「尻尾」を見つけたいと言いますCList a。どういう意味ですか？Haskell[a]タイプの場合、コンストラクターと、を使用する[]と:、これは明らかです。ヘッドはxinx: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's 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's 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

ですから、「しっぽ」は他のすべてだと思うかもしれません。問題は、「他のすべて」があなたのまたはのサブパートではないということです。この例を見てください：CListNNList

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

「頭」は1です。ただし、で定義されている構造のサブパートはexampleありませ2ん。それを得るには、元の形状とは異なる形状の新しい形状を作成する必要があります。それは可能ですが、率直に言って、初心者の練習としての価値はわかりません。31CList

「サブパート」の意味が明確でない場合は、例をツリーと考えてください。

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

サブパート=サブツリー。

于 2013-03-27T05:37:01.463 に答える
3

ヒント：同等性チェック（）ではなく、パターンマッチングのみを使用してこれを書き直してみてください==。

編集：

まず、パターンマッチングとは何か、そしてそれがどのように機能するかを理解することが重要です。ここに行って読んでおくことをお勧めします。ウェブ上にはこれに関する他のリソースもたくさんあります（Googleはあなたの友達です）。

それが済んだら、もう1つのヒントがあります。最初に関数を記述しnnListGet :: NNList a -> (a, CList a)、次にそれを使用してを実装しcListGetます。

于 2013-03-27T04:19:15.420 に答える
1

他の（非常に徹底的な）答えに追加するだけです。カスタムリストは折りたたみ可能な構造であることを理解しておくとよいでしょう。これは、一緒に組み合わせることができる一連の値を表すことを意味します。このようなデータ型は、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そこから、最大/最小、要素の検索など、で定義されているすべての関数を無料で取得できます。

いずれの場合も、 monoidを使用して、最初の要素を返すFoldableを実装できます。これは、左端の空でない要素を返す非常に単純なモノイドです。したがって、このモノイドを使用してのすべての要素を折りたたむと、最初の要素が得られます。headMaybeFirstFoldable

import Data.Monoid

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

（または、のインスタンスを使用foldrして直接使用することもできます。これにより、左端の空でない要素が返されます。MaybeAlternative

import Control.Applicative

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

。）

ただし、これは質問の2番目の部分であるコンピューティングを解決するものではありませんtailMaybe。これは、のような一般的な方法で定義することはできませんheadMaybe。そのためには、カスタム関数が必要になります。

参照：

于 2013-03-30T08:44:21.463 に答える
0

なぜそれを2つのタイプで宣言したのですか？正しい関数を使用した、一見より適切な型宣言を次に示します。

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)
于 2013-03-27T09:27:03.653 に答える