如何在 haskell 中递归调用子序列
How recursively call subsequences in haskell
我试图创建调用子序列的递归函数,但遇到了一些错误。
我的代码:
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次子序列吗?
抱歉我的英语不好
如果我用 1 调用你的函数,它将 return 一个元素列表的列表。如果我用 2 调用它,它将 return 元素列表的列表。在依赖类型的语言中,这很好,但是 Haskell 不是依赖类型的,因此您需要以其他方式表示结果,在结果类型中编码深度。
我没有太多使用多态递归,所以我想试试这个。这是我得到的:
{-# 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))
使用 singletons 非常简单。
{-# 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)
等等。
我试图创建调用子序列的递归函数,但遇到了一些错误。
我的代码:
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次子序列吗?
抱歉我的英语不好
如果我用 1 调用你的函数,它将 return 一个元素列表的列表。如果我用 2 调用它,它将 return 元素列表的列表。在依赖类型的语言中,这很好,但是 Haskell 不是依赖类型的,因此您需要以其他方式表示结果,在结果类型中编码深度。
我没有太多使用多态递归,所以我想试试这个。这是我得到的:
{-# 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))
使用 singletons 非常简单。
{-# 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)
等等。