CODEWITHSUNDEEP
stringhaskellprefixes
Dystr
Dystr

Reputation: 43

List of prefixes in haskell

I am to write a function which returns a list of all prefixes of a given string.

This is where I'm at so far. 

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

It compiles, but when I try running it on a string I get this:

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"

I am out of ideas. Any hints?

Upvotes: 0

Views: 3468

Answers (2)

Ingdas
Ingdas

Reputation: 1486

I don't think this code does what you think it does. You try to pattern match the list x with the pattern [x], which captures the element of a singleton list. If i fix your code like this, it works:

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

This gives the following result:

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

But you don't really need an accumulator for a function which calculates prefixes, I would write it like this:

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

This function is also available under the name "inits" in Data.List

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

Upvotes: 3

MiFi
MiFi

Reputation: 759

Point-free style solution for genereting list of all prefixes:

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

Upvotes: 0

Related Questions