計算Integer的`log`的函數

我寫了下面的函數。計算Integer的`log`的函數

f :: Integer -> Integer 
f x = if (odd x) then 0 else (floor . logBase 2) x

但會出現以下編譯時錯誤：

F.hs：2：31：（。）從使用的floor' Possible fix: add an instance declaration for (RealFrac Integer) In the first argument of產生」，即沒有例如用於（RealFrac整數） `floor' 在表達式中：floor。 logBase 2 在表達式：（地板logBase 2）×

F.hs：2：39：（。）否實例（浮動整數）從使用的logBase' Possible fix: add an instance declaration for (Floating Integer) In the second argument of產生」，即`logBase 2' 在表達式中：floor。 logBase 2 在表達式中：（floor。logBase 2）x失敗，模塊加載：無。

我該如何正確編寫上述函數？

來源

2014-10-17 Kevin Meredith

'fromIntegral'是你的朋友。 – luqui 2014-10-17 01:06:58

謝謝，luqui。這特別有用 - http://stackoverflow.com/a/1970515/409976。 – 2014-10-17 01:25:22

'地板。 logBase 2' =>'floor。 logBase 2。 fromIntegral' – user2407038 2014-10-17 01:42:02

這樣會稍微長一些，因爲我想不只是給你一些可行的代碼，而是深入解釋這個問題，這樣你就可以更好地理解GHC的類型錯誤。

前面已經回答簡單（和類型錯誤會盡可能地告訴你，雖然這肯定是不夠清晰），以使用logBase x y，這兩個參數x和y都必須是實例的「浮點「類型類。

尤其logBase是Floating類型類的方法（從Prelude's documentation）：

class Fractional a => Floating a where Source 
    logBase :: a -> a -> a

我們還發現，還從前奏：

class (Real a, Fractional a) => RealFrac a where Source 
    floor :: Integral b => a -> b

也就是說，爲了使用函數(floor . logBase)，我們需要兩個參數Fractional（因爲logBase需要這個）和Real（因爲floor需要bo日）。這兩者的合併被定義爲RealFrac，這正是GHC抱怨你沒有提供它（在你的函數的類型聲明中）。

爲什麼抱怨？從前奏中，我們找到RealFrac的以下instance聲明。請注意，「RealFrac Integer」丟失：

RealFrac Double 
RealFrac Float 
RealFrac CDouble  
RealFrac CFloat 
Integral a => RealFrac (Ratio a)  
HasResolution a => RealFrac (Fixed a)

方式Haskell的工作，就是如果你給它（不帶小數點連續數字）字面一個整數，就會認爲它屬於Integral類型類（和將試圖找出是否使其隱含地爲Integer或Int），但它將從永不隱含地將整數文字提升爲Fractional類之一（包括RealFrac）。由於沒有「RealFrac Integer」這一行，這意味着你不能期望Haskell編譯你的代碼。

您告訴Haskell您將通過顯式類型聲明爲它提供Integral實例（這就是爲什麼這些通常是個好主意的原因之一 - Haskell會默默接受您的函數聲明，否則只會拋出編譯在使用它的客戶端功能）錯誤：

f :: Integer -> Integer

的解決方案是通過使用下面的函數（Integral SIN轉換成任何兼容Num BER類型），以促進您的整數：

fromIntegral :: (Integral a, Num b) => a -> b

Floor執行相反方向的轉換（從Fractional到Integral），如其類型所示。

總之你需要簡單地說

f :: Integer -> Integer 
f x = if (odd x) then 0 else (floor . logBase 2.0 . fromIntegral) x

注意fromIntegral呼籲，請與編譯器期望是什麼，以及使用2.0（一Fractional文字）兼容的參數類型爲基地。

來源

2014-10-17 10:51:02 Zyxoas

歡迎使用Stack Overflow上的Haskell標籤，並做了詳細的解釋。 – AndrewC 2014-10-19 13:30:58

請注意，logBase需要轉換爲Floating類型，這可能會導致錯誤的結果。

f :: Integer -> Integer 
f x = if (odd x) then 0 else (floor . logBase 2.0 . fromIntegral) x 

λ> f (2^99999) 
    179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

這是因爲(2^99999 :: Double) = Infinity和floor Infinity明顯評估爲...一些令人驚訝。

的integer-logarithms包提供了integerLog2功能，效果更好：

λ> import Math.NumberTheory.Logarithms 

λ> integerLog2 (2^99999) 
    99999 
it :: Int

在integer-logarithms的功能僅僅是圍繞integer-gmp薄的包裝，所以你也可以用它直接：

λ> :set -XMagicHash 

λ> import GHC.Exts 

λ> import GHC.Integer.Logarithms 

λ> I# (integerLog2# (2^99999)) 
    99999 
it :: Int

注即使結果不是2的冪，這些函數也會返回一個值：

λ> integerLog2 1023 
    9

來源

2017-07-17 23:53:38

計算Integer的`log`的函數

回答

相關問題