1

サブシーケンスを呼び出す再帰関数を作成しようとしましたが、エラーが発生しました。

私のコード:

recursive 1 list = subsequences list
recursive n list = subsequences (recursive (n-1) list)

エラー：

Occurs check: cannot construct the infinite type: a1 ~ [a1]
    Expected type: [a1]
      Actual type: [[a1]]

    Relevant bindings include
      recursive :: a -> t -> [[a1]] (bound at p.hs:6:1)
    In the first argument of ‘subsequences’, namely
      ‘(recursive (n - 1) list)’
    In the expression: subsequences (recursive (n - 1) list)

この問題を解決したり、サブシーケンスを n 回呼び出す別の方法を見つけたりするのを手伝ってくれませんか?

下手な英語でごめんなさい

4

3 に答える 3

5

私は多態的再帰をあまり扱っていないので、これを試してみたかったのです。これが私が得たものです：

{-# LANGUAGE DeriveFunctor #-}

import Data.List (subsequences)

-- Any multiply-nested list such as a, [a], [[a]], [[[a]]], ...
data MultiList a
  = Leaf a
  | Nest (MultiList [a])
  deriving (Show, Functor)

recursive :: Int -> [a] -> MultiList [[a]]
recursive 1 list = Leaf (subsequences list)
recursive n list = Nest (fmap subsequences (recursive (n-1) list))
于 2015-06-23T18:10:44.120 に答える
3

singletonを使用するのは非常に簡単です。

{-# LANGUAGE GADTs, DataKinds, TypeFamilies, UndecidableInstances, TemplateHaskell, TypeOperators #-}

import Data.List
import Data.Singletons.TH
import Data.Singletons.Prelude
import qualified GHC.TypeLits as Lit

$(singletons [d| data Nat = Z | S Nat |])

type family Nested n a where
    Nested  Z    a = a
    Nested (S n) a = [Nested n a]

subsequenceses :: Sing n -> [a] -> [Nested n a]
subsequenceses  SZ     xs = xs
subsequenceses (SS sn) xs = subsequences (subsequenceses sn xs)

type family Lit i where
    Lit 0 = Z
    Lit n = S (Lit (n Lit.- 1))

type SLit n = Sing (Lit n)

main = print $ subsequenceses (sing :: SLit 2) [1..2]

subsequenceses (sing :: SLit 0) xsはxs

subsequenceses (sing :: SLit 1) xsはsubsequences xs

subsequenceses (sing :: SLit 2) xsはsubsequences (subsequences xs)

等々。

于 2015-06-23T21:13:37.667 に答える
1

関数を 1 で呼び出すと、要素のリストのリストが返されます。2 で呼び出すと、要素のリストのリストのリストが返されます。依存型付けされた言語ではこれで問題ありませんが、Haskell は依存型付けされていないため、別の方法で結果を表現し、結果の型の深さをエンコードする必要があります。

于 2015-06-23T17:28:38.090 に答える