Список префиксов в haskell

Question

Я должен написать функцию, которая возвращает список всех префиксов данной строки.

Вот где я сейчас нахожусь.

prefixess [x] [] = [x]
prefixess [] s = prefixess [s] s
prefixess [x] s  = prefixess [x, (init s)] (init s)
prefixes s = prefixess [] s

Он компилируется, но когда я пытаюсь запустить его на строке, я получаю это:

Couldn't match type ‘Char’ with ‘[t]’
Expected type: [[t]]
  Actual type: [Char]
Relevant bindings include
  it :: [t] -> [[t]] (bound at <interactive>:18:1)
In the first argument of ‘prefixess’, namely ‘"abcde"’
In the expression: prefixess "abcde"
In an equation for ‘it’: it = prefixess "abcde"

У меня нет идей. Есть намеки?

Answer 1

Я не думаю, что этот код делает то, что вы думаете, что он делает. Вы пытаетесь сопоставить шаблону список x с шаблоном [x], который захватывает элемент одноэлементного списка. Если я исправлю ваш код следующим образом, он будет работать:

prefixess x [] = x
prefixess [] s = prefixess [s] s
prefixess x s  = prefixess ((init s):x) (init s)
prefixes s = prefixess [] s

Это дает следующий результат:

Main> prefixes "stackru"
["","s","st","sta","stac","stack","stacko","stackov","stackove","stackover","stackoverf","stackoverfl","stackoverflo","stackru"]

Но вам не нужен аккумулятор для функции, которая вычисляет префиксы, я бы написал так:

prefixes' (x:xs) = [] : (map (x:) (prefixes xs))
prefixes' [] = [[]]

Эта функция также доступна под именем "inits" в Data.List

Main> import Data.List
Main Data.List> inits "stackru"
["","s","st","sta","stac","stack","stacko","stackov","stackove","stackover","stackoverf","stackoverfl","stackoverflo","stackru"]

Answer 2

Бесточечное решение для генерации списка всех префиксов:

prefixes = foldr (\el acc -> [] : map (el:) acc) [[]]