Implementando a função de caudas em Haskell - haskell

Eu estou tentando implementar a função tails. Esta é minha tentativa:

tails" :: [a] -> [[a]]
tails" [] = []
tails" (x:xs) = xs:[[tails" xs]]

Eu continuo correndo em erros de compilação:

Couldn"t match expected type ‘a’ with actual type ‘[[a]]’
‘a’ is a rigid type variable bound by
the type signature for tails" :: [a] -> [[a]] at..

O que há de errado com minha implementação?

Respostas:

5 para resposta № 1

Substituir

tails" (x:xs) = xs:[[tails" xs]]

com:

tails" (x:xs) = xs : tails" xs

---

4 para resposta № 2

Além do sintaxe erro de tipo, sua implementação não está correta (para a especificação). Compare com este ...

Prelude> let tails [] = [[]]
Prelude|     tails y@(x:xs) = y:(tails xs)
Prelude|
Prelude> tails "abc"
["abc","bc","c",""]

---

1 para resposta № 3

Já faz mais de um ano, mas nenhuma resposta correta foi dada, então aqui está minha opinião sobre isso.

Vamos começar com a assinatura do tipo:

tails" :: [a] -> [[a]]

Isso sugere que tails" deve retornar uma lista de listas. O caso terminal que você solucionou é apenas uma lista vazia. Altere para:

tails" [] = [[]]

Agora, o caso geral. Vamos "s assumir que nossa tails" funciona da maneira que queremos:

tails" []      -> [[]]
tails" [1]     -> [[1], []]
tails" [2,1]   -> [[2,1], [1], []]
tails" [3,2,1] -> [[3,2,1], [2,1], [1], []]

Como podemos ver, queremos incluir a lista original e a lista vazia. Isso significa que, dada uma lista de entrada xs, queremos concatenar xs para algo mais.

Mas o que é isso? algo mais? Vamos fazer um pouco de matemática pseudo-haskell:

let A = tails" [3,2,1] = [[3,2,1], [2,1], [1], []]
let B = tails" [2,1] = [[2,1], [1], []]
=> A = [[3,2,1], B] -- (1)

tail [3,2,1] == [2,1]
=> B = tails" (tail [3,2,1]) -- (2)

By (1) and (2)
A = [[3,2,1], tails" (tail [3,2,1])]
=> tails" [3,2,1] = [[3,2,1], tails" (tail [3,2,1])] -- (3)

By replacing [3,2,1] in (3) with xs
tails" xs = [xs, tails" (tail xs)]

Traduzir tudo isso para Haskell nos dá:

tails" :: [a] -> [[a]]
tails" [] = [[]]
tails" xs = xs : (tails" $ tail xs)


main = do
print $ tails" [1,2,3]

-- [[1,2,3],[2,3],[3],[]]

---

1 para resposta № 4

tails é o exemplo canônico com listas simples para o esquema de recursão chamado paramorfismo. O exemplo a seguir usa o esquemas de recursão biblioteca de Edward Kmett:

import Data.Functor.Foldable
import Data.List (tails)                      -- just for our test

paratails :: [a] ->  [[a]]
paratails = para alg where
alg :: ListF a ([a], [[a]]) -> [[a]]
alg (Cons x (hs, res)) = (x : hs) : res
alg Nil = [[]]

-- $
-- >>> paratails [1,2,3,4]
-- [[1,2,3,4],[2,3,4],[3,4],[4],[]]
-- >>> paratails []
-- [[]]
-- >>> paratails [1,2,3,4] == (tails [1,2,3,4])
-- True
-- >>> paratails [] == (tails [])
-- True

Nota: Para encurtar o código, você pode usar LambdaCase. Com esta extensão, no entanto, você não pode especificar a assinatura do tipo alg função

---

1 para resposta № 5

Como agora há um esquemas de recursão resposta dobra, sinto-me obrigado a adicionar um esquemas de recursão desdobramento resposta:

import Data.Functor.Foldable

tailsApo :: [a] -> [[a]]
tailsApo = apo coalgTails
where
coalgTails = case
[] -> Cons [] (Left [])
li@(_:xs) -> Cons li (Right xs)

Eu usei um apomorfismo em vez de um anamorfismo simples porque não queremos produzir uma lista vazia de uma lista vazia (tails [] == [[]]).

---