Haskell comparing two lists' lengths but one of them is infinite?-CodePudding

I want to write a function that checks if the first list is longer than the second list and one of them can be infinite. However I can't find a working solution.

isLonger :: [a] -> [b] -> Bool
isLonger a b 
        | listLength a > listLength b = True
        |otherwise = False

listLength :: [a] -> Integer
listLength = foldr (flip $ const . ( 1)) 0

CodePudding user response：

@dfeuer's solution wins on cleverness, but in terms of a more typical solution...

A reasonable approach mentioned in the comments is to process both lists in parallel and figure out which one "runs out" first -- that's the shorter list. A simple solution is to recurse while both lists are non-empty:

isLonger :: [a] -> [b] -> Bool
isLonger (x:xs) (y:ys) = isLonger xs ys

and return an answer as soon as one of the lists becomes empty:

isLonger []     _  = False   -- list a <= list b
isLonger _      [] = True    -- list a > list b

If both lists run out at the same time (equal length), the first pattern will match, so that will determine the answer in case of a tie.

CodePudding user response：

Plain old natural numbers will not do the trick, because you can't calculate the natural number length of an infinite list in finite time. However, lazy natural numbers can do it.

import Data.Function (on)

data Nat = Z | S Nat
  deriving (Eq, Ord)

len :: [a] -> Nat
len = foldr (const S) Z

isLonger :: [a] -> [b] -> Bool
isLonger = (>) `on` len

You can do it even more compactly using lists to represent lazy natural numbers.

isLonger :: [a] -> [b] -> Bool
isLonger = (>) `on` (() <$)

Of course, if both lists are infinite, you are doomed to an infinite loop no matter what you do.