8

Haskellers と Haskellettes さん、こんにちは。

http://learnyouahaskell.com/を読んでいるときに、私の友人が問題を思いつきました:

Haskell で、すべての sub-sub-_-sublists が空の場合に True を返す再帰関数を作成することは可能ですか? 私の最初の推測は-そうあるべきですが、型注釈を書くだけで大きな問題があります。

彼は次のようなことを試しました

nullRec l = if null l
               then True
               else if [] `elem` l
                    then nullRec (head [l]) && nullRec (tail l)
                    else False

これは-機能していません-:-)

私は次のようなものを思いついた

  • concat を使用した折りたたみ - 単一の長いリストを取得する
    (実装に問題が発生する)
  • または無限のツリーのようなデータ型を作成し、リストからこれを作成します
    （まだ実装していません）

しかし、後者は、この問題に対して少しやり過ぎのように思えます。あなたのアイデアは何ですか - このような晴れた日曜日に ;-)

前もって感謝します

すべてのコメントへの反応として - これはスタイルが悪いので追加したいのですが、これは単なる実験です !
家でこれを試さないでください！;-)

4

2 に答える 2

5

型クラスはどうですか？

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}

class NullRec a where
  nullRec :: a -> Bool

instance NullRec a => NullRec [a] where
  nullRec [] = True
  nullRec ls = all nullRec ls

instance NullRec a where
  nullRec _  = False

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]])
于 2011-07-10T15:34:52.837 に答える
4

これは、次の理由により、パラメトリック ポリモーフィズムのみを使用して行うことはできません。

次の値を考慮してください。

x = [8] :: [Int]
y = [3.0] :: [Double]
z = [[]] :: [[Int]]

x明らかに、関数は と の両方で機能するy必要があるため、その型は でなければなりませんnull1 :: [a] -> Bool。(誰かがこの引数を正式に見せるのを手伝ってくれませんか? これが[Int] -> Booland で単一化可能な唯一の最も具体的な文脈のない型であることをどのように示すことができます[Double] -> Boolか? 型間のその関係の名前はありますか?)

現在、このタイプを持っている場合、抽象化されたリスト要素の値のみが異なるため、null1 zと等しくなります。(再び正式な証明にはほど遠い:()null1 x

あなたが望むのzはでありnull2 :: [[a]] -> Bool、これは動作が異なるため、 とnull1同じnull2名前を指定するにはオーバーロードが必要になります。（FUZxxlの回答を参照）

于 2011-07-10T16:03:25.090 に答える