I have a few questions about this Haskell function-CodePudding

prefix :: String -> String -> Bool
prefix [] _ = True
prefix _ [] = False
prefix (x:xs) (y:ys) = (x == y) && (prefix xs ys)

I have this Haskell function in which we check whether the first string is the prefix of the other one.

I can't really understand a few things.

Why is prefix [] _ True? And why is it false the other way around? I mean if both are empty shouldn't it be true that nothing is a prefix of nothing?

Also, am I understanding how the function works correctly?

We take the first symbol from the first string and then we take the first symbol from second string and see whether they are equal and then we call the same function with the strings shorter by one character?

Also, we use the prefix implemention to create a function substring which checks whether one string is part of another one

substring :: String -> String -> Bool
substring x y
    | length x > length y = False
    | otherwise = prefix x y || substring x (tail y)

I am also having trouble understanding how the substring function works in general. Why is it necessarily a prefix if the length x is bigger than y?

CodePudding user response：

We take the first symbol from the first string and then we take the first symbol from second string and see whether they are equal and then we call the same function with the strings shorter by one character?

Your understanding of how the function works is correct.

The function takes 2 string arguments, and checks if the first one is a prefix of the second. The empty string [] is always a prefix to any other string, and that's why it return True for the input [] _. The other way around is not true, the non empty string x is not a prefix of the empty string y.

CodePudding user response：

I mean if both are empty shouldn't it be true that nothing is a prefix of nothing?

If both are empty, then the first clause will fire and thus return True. The first clause says nothing about the second parameter. It simply says "If the first list is empty, then it is True. This thus means that we know in the second clause that the first list is not empty.

Also, am I understanding how the function works correctly?

The first clause says that if the prefix is an empty list, then the first list is a prefix of the second list. The second clause says if the string is empty (and the prefix is not empty), then the first list is not a prefix of the second.

Finally the last clause says, if both lists are not empty, then the first list is a prefix of the second list if the first elements of the two lists are the same, and the tail of the prefix is a prefix of the tail of the string. This last clause will thus move the cursor one to the right of both list, and checks if the remaining prefix is a prefix of the remaining string.