Блог

Главная - Вопросы по программированию - Haskell: как применить частичный порядок к функции подстроки?

Haskell: как применить частичный порядок к функции подстроки?

#haskell #substring #partial-ordering

#haskell #подстрока #частичный порядок

Вопрос:

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

Теперь я хочу применить класс POrd к функции подстроки, чтобы сделать так, чтобы подстроки могли быть частично упорядочены.

Однако я застрял на том, как правильно применить класс частичного порядка (POrd) к функции подстроки.

  class Eq a => POrd a where

     pocompare :: a -> a -> Maybe Ordering
     (~<), (~>), (~<=), (~>=) :: a -> a -> Bool

       -- Minimal complete definition: (~<=) | pocompare
 
     pocompare x y | x == y       = Just EQ
                  | x ~<= y      = Just LT
                  | y ~<= x      = Just GT
                  | otherwise    = Nothing

     x ~<= y = pocompare x y ==  Just LT
     x ~<  y = x ~<= y amp;amp; x /= y
     x ~>= y = y ~<= x
     x ~>  y = x ~>= y amp;amp; x /= y

 
  substring :: Eq a => [a] -> [a] -> Bool
 substring []_= True
 substring _[]     = False
 substring p@(x:xs) (y:ys) = x == y amp;amp; prefix xs ys || substring p ys
  where
    prefix []     _= True
    prefix _[]     = False
    prefix (a:as) (b:bs) = a == b amp;amp; prefix as bs
 
  instance POrd a => POrd [a] where
  (~<=) = substring

  xs ~<= ys = substring xs ys
  xs ~>= ys = substring ys xs

Комментарии:

1. Я думаю, вам следует удалить последние две строки. Помимо этого, я не вижу ничего плохого прямо сейчас.

2. Значит, минимальное определение в конце не обязательно?

3. Комментарий «минимальное определение» в POrd классе указывает, что вам нужно определение для или ~<= или pocompare . В вашем POrd [a] экземпляре вы определяете ~<= , а затем у вас есть еще две строки определений.

4. Возможно, это просто незначительный момент, но я думаю, что название substring совершенно неверно, когда функция применяется к более общим спискам, а не только к строкам. И на самом деле, эта функция уже есть в стандартной библиотеке как isInfixOf

5. @pedrofurla, насколько я знаю, да. Это просто странное форматирование, посмотрите _= на предыдущую строку.