CODEWITHSUNDEEP
haskell
mljohns89
mljohns89

Reputation: 915

Making inits function in Haskell

Alright so here is an interesting situation (imo)

Here's my code:

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

inits' :: [a] -> [[a]]
inits' [] = []
inits' (x:xs) = init(x:xs) : inits' xs

eightB :: (Eq a) => [a] -> [a] -> Bool

eightB xs ys = elem xs (tails' ys ++ inits' ys)

I'm trying to solve the "Needle in a Haystack" problem from Learn You a Haskell For Great Good; in my own way.

The problem I'm running into is, when I try inputting:

inits' [1,2,3,4,5]

into ghci, I get:

[[1,2,3,4],[2,3,4],[3,4],[4],[]]

The function works fine for the first iteration, but for some reason decides to switch to the tail function after the first iteration (at least that's what I think is happening).

Upvotes: 1

Views: 3247

Answers (5)

CoolCode
CoolCode

Reputation: 1

I just solved this for an assigment in uni: I think this a clean way to go about it. You can also write the helper function using map (put in comment above)

    --add x xss = map (x :) xss

    add :: a -> [[a]] -> [[a]]
    add x [] = []
    add x (xs:xss) = (x:xs) : add x xss

    inits :: [a] -> [[a]]
    inits []     = [[]]
    inits (x:xs) = [] : add x (inits xs)

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

Upvotes: 0

fp_mora
fp_mora

Reputation: 714

There is one huge problem with using init in inits, that is, init cannot return anything meaningful nor correct with an infinite list.

There are alternatives for inits

The simplest is

[ [1..i] | i <- [1..] ]

It will output forever. It is wise to use take with it.

Functions should approach total functions.

ins ls = [ take i ls | i <- [1..] ]

take 6 $ ins ['a'..]
["a","ab","abc","abcd","abcde","abcdef"]

These are infinite tails functions. The first, numbers only. The second, any.

> tlsn  =  [ replicate i i | i <- [1..] ]
> tls xs = [ replicate i x |(i,x) <- zip [1..] xs ]
> take 5 tlsn
[[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5]]

This is tails and a transposition of tails, both from top to bottom

1 2 3 4 5    1
  2 3 4 5    2 2
    3 4 5    3 3 3
      4 5    4 4 4 4
        5    5 5 5 5 5 

> transpose.take 5 $ tlsn
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5]]

transpose will not transpose an infinite list.

What to do?

Upvotes: -1

dfeuer
dfeuer

Reputation: 48581

I know this is several years old, but figured I'd mention that inits' is not really useful for producing an implementation of the search/isInfixOf function. Your code above checks to see whether the needle is equal to one of the tails or one of the inits, not whether it's contained somewhere. Now if you actually do want to calculate your eightB function for some reason, you can do so much more cheaply:

eightB xs ys =
  (xs `isPrefixOf'` ys)
  || (reverse xs `isPrefixOf'` reverse ys)

xs `isPrefixOf'` ys = and (zipWith (==) xs ys)

Upvotes: 1

jamshidh
jamshidh

Reputation: 12060

The problem is, there is a sort of inherent tail function in your pattern matching in inits'.

inits' (x:xs) = ....

This breaks up the list into two parts

x = head theList
xs = tail theList

When you recurse, you are only using the tail part

inits' (x:xs) = <stuff ....> : inits' xs

What you really want to do is pass the init of the list into the recursion. Unfortunately, you can't break up a list into init and last using pattern matching. You can do this easily in a where though.

This is probably what you want to do

inits' :: [a] -> [[a]]
inits' [] = []
inits' theList = i:inits' i
  where
    i = init theList

Upvotes: 0

mljohns89
mljohns89

Reputation: 915

@Iuqui helped me get to this answer.

inits' :: [a] -> [[a]]
inits' [] = []
inits' xs = init xs : inits' (init xs)

Upvotes: 2

Related Questions