3

アイデアは、全体の長さを計算せずにリストの長さを Int と比較する「遅延」長さ関数を実装することです。

{-# LANGUAGE DeriveFunctor
           , TypeFamilies
           , FlexibleInstances #-}
import Data.Functor.Foldable

type instance Base Int   = Maybe

これで、Foldable / Unfoldable を持つことができます

instance Foldable Int where
  project 0 = Nothing
  project x = Just (x-1)

instance Unfoldable Int where
  embed Nothing  = 0
  embed (Just x) = x+1

[a] を Base Int Int に変換したい:

leng :: [a] -> Base Int Int
leng = ana phi where
  phi :: [a] -> Base Int [a]
  phi []    = Nothing
  phi (_:t) = Just t

しかし、これはうまくいきません。[a] と不平を言う -> Base (Maybe Int) [a] は phi の型として期待されます。理由がわかりません。

それがうまくいった場合、私は比較することができます：

gt = curry $ hylo psi phi where
  phi (Just _, Nothing)  = Left True
  phi (Nothing, _)       = Left False
  phi (Just t, Just n)   = Right (t, n)

  psi (Left t)  = t
  psi (Right t) = t

main = print $ (leng [1..]) `gt` (ana project 4)

長さの何が問題になっていますか？

4

4 に答える 4

3

型違いのご指摘ありがとうございます。タイプを正しくすることで、考えが明確になりました:)

{-# LANGUAGE DeriveFunctor
           , TypeFamilies
           , FlexibleInstances #-}
import Data.Functor.Foldable

type instance Base ([a], Int) = Either Bool

instance Foldable ([a], Int) where
  project ([], _) = Left False
  project (_, 0) = Left True
  project ((h:t), n) = Right (t, n-1)

longerThan :: [a] -> Int -> Bool
longerThan = curry $ cata $ either id id

main = print $ [1..] `longerThan` 4

満足し？これを拡張して、私が実際にこれらすべてを開始した理由を示しましょう。

{-# LANGUAGE DeriveFunctor
           , TypeFamilies
           , FlexibleInstances
           , FlexibleContexts
           , UndecidableInstances #-}
import Data.Functor.Foldable

data Zip a b x = Z (Base a (Base b x))
instance (Functor (Base a), Functor (Base b)) => Functor (Zip a b) where
  fmap f (Z a) = Z $ fmap (\x -> fmap f x) a

type instance Base (a, b) = Zip a b

ヒントはありますか？両方の構造を同時に再帰できます!

instance (Foldable a, Foldable b) => Foldable (a, b) where
  project (a, b) = Z $ fmap (\x -> fmap (\y -> (x,y)) $ project b) $ project a

デモ: Base Int を導入し、リストの長さが指定された Int より大きいことを確認します。

type instance Base Int = Maybe

instance Foldable Int where
  project 0 = Nothing
  project x = Just $ x-1

-- lt and gt are the same;
-- just showing off with the order of arguments, so you can appreciate Zip
lt :: Int -> [a] -> Bool
lt = curry $ cata phi where
  phi (Z Nothing) = True
  phi (Z (Just Nil)) = False
  phi (Z (Just (Cons _ t))) = t

gt :: [a] -> Int -> Bool
gt = curry $ cata phi where
  phi (Z (Cons _ Nothing)) = True
  phi (Z Nil) = False
  phi (Z (Cons _ (Just t))) = t

main = print [[1..] `gt` 4, 4 `lt` [1..]]
于 2013-08-28T15:09:13.343 に答える
2

これは、型ファミリでそれを行うという演習の目的を無効にする可能性がありますが、単に「リストの長さを int と遅延比較する」関数が必要な場合は、直接記述できます。

cmp :: [a] -> Int -> Ordering
cmp [] n = compare 0 n
cmp (_:xs) n = if n <= 0 then GT else cmp xs (n - 1)
于 2013-08-28T13:55:49.857 に答える
0

@PaulVisschers が実装している同じ関数は、実際に必要なことを行うための最も簡単な方法の 1 つであり、何らかの理由でFoldables を使用した演習が必要な場合は、カタモルフィズムを使用して実装できます。

import Data.Functor.Foldable

cmp :: [a] -> Int -> Ordering
cmp = cata psi

psi :: Base [a] (Int -> Ordering) -> Int -> Ordering
psi Nil n = compare 0 n
psi (Cons h t) n = if n <= 0 then GT else t (n-1)
于 2013-08-28T15:04:05.527 に答える