Прополка дубликатов из списка функций

Question

Можно ли удалить дубликаты (как в nub) из списка функций в Haskell? В принципе, это можно добавить экземпляр (Eq (Integer -> Integer))

В GHCI:

let fs = [(+2), (*2), (^2)] 
let cs = concat $ map subsequences $ permutations fs 
nub cs 

<interactive>:31:1: 
No instance for (Eq (Integer -> Integer)) 
    arising from a use of `nub' 
Possible fix: 
    add an instance declaration for (Eq (Integer -> Integer)) 
In the expression: nub cs 
In an equation for `it': it = nub cs 

Спасибо заранее.

...

Далее, на основании ответа larsmans', теперь я в состоянии сделать это

> let fs = [AddTwo, Double, Square] 
> let css = nub $ concat $ map subsequences $ permutations fs 

для того, чтобы получить эту

> css 

[[],[AddTwo],[Double],[AddTwo,Double],[Square],[AddTwo,Square],[Double,Square],[AddTwo,Double,Square],[Double,AddTwo],[Double,AddTwo,Square],[Square,Double],[Square,AddTwo],[Square,Double,AddTwo],[Double,Square,AddTwo],[Square,AddTwo,Double],[AddTwo,Square,Double]] 

, а затем этот

> map (\cs-> call <$> cs <*> [3,4]) css 

[[],[5,6],[6,8],[5,6,6,8],[9,16],[5,6,9,16],[6,8,9,16],[5,6,6,8,9,16],[6,8,5,6],[6,8,5,6,9,16],[9,16,6,8],[9,16,5,6],[9,16,6,8,5,6],[6,8,9,16,5,6],[9,16,5,6,6,8],[5,6,9,16,6,8]] 

, который был моим первоначальным намерением.

Answer 1

Нет, это невозможно. Функции не могут сравниваться для равенства.

Причина этого заключается в том:

1. сравнение Указатель делает очень мало смысла для функций Haskell, так как тогда равенство id и \x -> id x будет меняться в зависимости от того, последняя форма оптимизирована в id.
2. Экстремальное сравнение функций невозможно, так как это потребует положительного решения проблемы остановки (обе функции, имеющие одно и то же поведение при остановке, являются необходимым требованием равенства).

Для устранения этой проблемы для представления функций в качестве данных:

data Function = AddTwo | Double | Square deriving Eq 

call AddTwo = (+2) 
call Double = (*2) 
call Square = (^2) 

Answer 2

Нет, это не возможно сделать это для Integer -> Integer функций.

Однако, это является возможно, если вы также хорошо с более общим типом подписью Num a => a -> a, так как ваш пример показывает! Один наивный способ (не безопасно), будет идти, как

{-# LANGUAGE FlexibleInstances   #-} 
{-# LANGUAGE NoMonomorphismRestriction #-} 

data NumResLog a = NRL { runNumRes :: a, runNumResLog :: String } 
      deriving (Eq, Show) 

instance (Num a) => Num (NumResLog a) where 
    fromInteger n = NRL (fromInteger n) (show n) 
    NRL a alog + NRL b blog 
      = NRL (a+b) ("("++alog++ ")+(" ++blog++")") 
    NRL a alog * NRL b blog 
      = NRL (a*b) ("("++alog++ ")*(" ++blog++")") 
    ... 


instance (Num a) => Eq (NumResLog a -> NumResLog a) where 
    f == g = runNumResLog (f arg) == runNumResLog (g arg) 
    where arg = NRL 0 "THE ARGUMENT" 

unlogNumFn :: (NumResLog a -> NumResLog c) -> (a->c) 
unlogNumFn f = runNumRes . f . (`NRL`"") 

, который работает в основном путем сравнения «нормализованная» версии исходного кода функций. Конечно, это не удается, когда вы сравниваете, например. (+1) == (1+), которые эквивалентны, но дают "(THE ARGUMENT)+(1)" против "(1)+(THE ARGUMENT)" и поэтому обозначаются как неравные. Однако, поскольку функции Num a => a->a по существу сжимаются как многочлены (да, abs и signum сделать это немного сложнее, но это все еще возможно), вы можете найти тип данных, который должным образом обрабатывает эти эквивалентности.

Материал может быть использован, как это:

> let fs = [(+2), (*2), (^2)] 
> let cs = concat $ map subsequences $ permutations fs 
> let ncs = map (map unlogNumFn) $ nub cs 
> map (map ($ 1)) ncs 
[[],[3],[2],[3,2],[1],[3,1],[2,1],[3,2,1],[2,3],[2,3,1],[1,2],[1,3],[1,2,3],[2,1,3],[1,3,2],[3,1,2]]