Вопросы Теги

Локальный минимум в Haskell [дубликат]

Вы можете использовать оператор sizeof, но он не будет работать для функций, потому что для ссылки на указатель вы можете сделать следующее, чтобы найти длину массива: 

len = sizeof(arr)/sizeof(arr[0])

Код, первоначально найденный здесь : C программа для поиска числа элементов в массиве

1
задан dziulis 8 February 2018 в 19:51
поделиться

3 ответа

Я решил бы это, как описано Томасом М. Дюбусоном. Поскольку мы хотим, чтобы концы списка «подсчитывались», мы добавим отрицательные бесконечности к каждому концу, прежде чем создавать тройки. Пакет monoid-extras обеспечивает подходящий тип для этого. 

import Data.Monoid.Inf

pad :: [a] -> [NegInf a]
pad xs = [negInfty] ++ map negFinite xs ++ [negInfty]

triples :: [a] -> [(a, a, a)]
triples (x:rest@(y:z:_)) = (x,y,z) : triples rest
triples _ = []

isBig :: Ord a => (a,a,a) -> Bool
isBig (x,y,z) = y > x && y > z

scnd :: (a, b, c) -> b
scnd (a, b, c) = b

finites :: [Inf p a] -> [a]
finites xs = [x | Finite x <- xs]

largest :: Ord a => [a] -> [a]
largest = id
    . finites
    . map scnd
    . filter isBig
    . triples
    . pad

Кажется, что он работает надлежащим образом; в ghci: 

> largest [0,1,5,2,3,7,8,4]
[5,8]
> largest [10,1,10]
[10,10]
> largest [3]
[3]
> largest []
[]

Вы можете также рассмотреть возможность объединения finites, map scnd и filter isBig в одном понимании списка (затем исключая определения finites, scnd и isBig): 

largest :: Ord a => [a] -> [a]
largest xs = [x | (a, b@(Finite x), c) <- triples (pad xs), a < b, c < b]

Но мне нравится разложенная версия лучше; функции finites, scnd и isBig могут оказаться полезными в других местах вашего развития, особенно если вы планируете построить несколько вариантов этого для разных нужд.

3
ответ дан Daniel Wagner 15 August 2018 в 20:48
поделиться

Одна вещь, которую вы можете попробовать, это смотреть. (Thomas M. DuBuisson предложил другой, который также будет работать, если вы правильно обработаете окончательный один или два элемента.) Поскольку кажется, что это проблема, которую вы хотите решить самостоятельно, как упражнение для обучения, я напишу скелет, который вы можете взять в качестве отправной точки, если хотите: 

largest :: [Integer] -> [Integer]
largest [] = _
largest [x] = _ -- What should this return?
largest [x1,x2] | x1 > x2   = _
                | x1 < x2   = _
                | otherwise = _
largest [x1,x2,x3] | x2 > x1 && x2 > x3 = _
                   | x3 > x2 = _
                   | otherwise = _
largest (x1:x2:x3:xs) | x2 > x1 && x2 > x3 = _
                      | otherwise          = _

В дополнение к (x1:x2:x3:[]) нам нужен специальный случай [x1,x2,x3], поскольку, согласно пояснению вашего комментария, largest [3,3,2] должен вернуться []. но largest [3,2] должен вернуться [3]. Поэтому последние три элемента требуют специальной обработки и не могут просто перезаписываться на последних двух.

Если вы также хотите, чтобы результат включал заголовок списка, если он больше второго элемента, вы должны сделайте это вспомогательной функцией, а ваш largest будет похож на largest (x1:x2:xs) = (if x1>x2 then [x1] else []) ++ largest' (x1:x2:xs). То есть вам нужна специальная обработка для первых элементов исходного списка, которые вы не хотите применять ко всем подспискам, когда вы рекурсируете.

2
ответ дан Davislor 15 August 2018 в 20:48
поделиться
  • 1
    Я думаю, вы хотели использовать largest (x2 : x3 : xs) в вашем примере последнего случая? Способ структурирования кода, чтобы избежать этой проблемы, - это фраза последнего шаблона как x1 : xs@(x2 : x3 : _), а затем повторение с помощью только largest xs. – Jon Purdy 9 February 2018 в 15:40
  • 2
    @JonPurdy Нет, идея состоит в том, что нам нужно добавить первый элемент, если он больше второго, но в рекурсивном помощнике мы никогда не добавляем первый элемент x1. Рекурсивный помощник сравнивает x2 с обоими x1 и x3 и никогда не добавляет x1. Поэтому мы вызываем его в списке original . – Davislor 9 February 2018 в 19:28
  • 3
    @JonPurdy Однако синтаксис x1:@xs(x2:x3:_) отлично работает и может быть менее подвержен ошибкам. Хорошее предложение. – Davislor 9 February 2018 в 19:29
  • 4
    Ах, я вижу, что вы получаете, это была моя ошибка. – Jon Purdy 10 February 2018 в 07:59

Как было предложено в комментариях, одним из подходов было бы сначала сгруппировать список в кортежи длины 3, используя прелюдии zip3 и tail : 

*Main> let xs = [0,1,5,2,3,7,8,4]
*Main> zip3 xs (tail xs) (tail (tail xs))
[(0,1,5),(1,5,2),(5,2,3),(2,3,7),(3,7,8),(7,8,4)]

Который имеет тип: [a] -> [b] -> [c] -> [(a, b, c)] и [a] -> [a] соответственно.

Далее вам нужно найти способ отфильтровать кортежи, где средний элемент больше, чем первый и последний. Одним из способов было бы использовать функцию Preludes filter : 

*Main> let xs = [(0,1,5),(1,5,2),(5,2,3),(2,3,7),(3,7,8),(7,8,4)]
*Main> filter (\(a, b, c) -> b > a && b > c) xs
[(1,5,2),(7,8,4)]

Который имеет тип: (a -> Bool) -> [a] -> [a]. Это отфильтровывает элементы списка, основанные на булевом возврате из переданного предиката.

Теперь для последней части вам нужно извлечь средний элемент из фильтрованных кортежей выше. Вы можете сделать это легко с помощью функции Прелюдии map : 

*Main> let xs = [(1,5,2),(7,8,4)]
*Main> map (\(_, x, _) -> x) xs
[5,8]

Какой тип: (a -> b) -> [a] -> [b]. Эта функция отображает элементы из списка типов a в b.

Вышеупомянутый код, сшитый вместе, будет выглядеть так: 

largest :: (Ord a) => [a] -> [a]
largest xs = map (\(_, x, _) -> x) $ filter (\(a, b, c) -> b > a && b > c) $ zip3 xs (tail xs) (tail (tail xs))

Обратите внимание, что здесь я использовал typeclass Ord, так как приведенный выше код должен сравниваться с > и <. Здесь все-таки держать его как Integer.

0
ответ дан RoadRunner 15 August 2018 в 20:48
поделиться
Другие вопросы по тегам:

Похожие вопросы: