如何在编译时在haskell中进行边界检查？ [英] How to do bounds-checking in haskell at compile-time?

问题描述

我对Haskell相当陌生，我想知道如何使用类型系统强制执行边界。阅读此问题并查看关于智能构造函数的链接文章我想我可以生成一个有界类型并为其生成一个构造函数例如：

pre $ data概率a = P a派生（Show，Ord，Eq）


我读过学习你一个很棒的Haskell ，你应该不会在数据中添加类型类型约束

声明

所以此时没有类型限制...

<$ p
maxBound = P 0
maxBound = P 1

smartP ::（Floating a）=>实例有界概率其中
minBound = P 0
maxBound = P 1

a - >概率
smartP x = assert（0 <= x&& x <= 1）$ P x

现在我想知道的是，如何以及如何在编译时为边界检查一个不容易用 Peano号码（如Double ...）。也许如果可能的话，我们将如何去寻找一个不可枚举但有界的类型的编码。

此外：概率是数字，我希望它们的行为类似于数字（有+ - *等在他们的工作，如你所料）。是否可以通过使 Number type-class（通过派生或其他方式）使 Probability 部分来实现此行为这不涉及以明显的方式手工编码所有功能）？

非常感谢您的任何解释。

将您的问题解释为表示无效状态不可表示的概率的最佳方式是什么，并对此进行冗余。我不是专家，不知道这是否会对您有所帮助。

---

我们假设也许不正确）你原本是从样本计算概率。你的 succes 和 try 都是内存中的整数。我们甚至假设它们是任意精度的（在haskell Integer 中）。

除了它们可以被计算很快，IEEE浮点并不是表示概率的好方法（请参阅这里）：

• 当您从0移动到1.0时，它们变得不那么密集，所以如果您关心精度不能自由地在事情发生的概率和它没有发生之间转换


• 这是浪费的：大多数可表示的值在0-1范围之外




从我上面链接的博客文章中，我们了解到使用可能性而不是概率改善了情况（我们使有用值的数量增加了一倍），并且在特定的 log-odds 通过拉伸浮点数的密集区域并压缩稀疏区域解决了上述第一个问题。





记录空间中的赔率





我在


$ b $ b

log-odds 只是一些基数的对数（所以我们使用 logOdds code> / 如果我们想要概率）。我们可以在ghci中使用它，并很快得到直觉：



  Prelude>让logOdds成功试试= logBase 10（成功/（尝试 - 成功））
前奏> logOdds 1 2 
 0.0 
 Prelude> logOdds 1 10 
 -0.9542425094393249 
 Prelude> logOdds 5 1000 
 -2.2988530764097064 
 Prelude> logOdds 995 1000 
 2.2988530764097064 
 Prelude> logOdds 99995 100000 
 4.301008280396999 
 Prelude> logOdds 9999995 10000000 
 6.3010297785166856 
  

我们可以看到整个浮点域现在很有用，而且我们可以在可能性和不可能性之间进行转换，而不会损失精度。也有人认为，使用这些数字进行直觉决策更容易。





因此， log-odds 表示同构于无效状态不可表示的概率。我们可以转换回来

  Prelude> （1  - （1 /（1 +（10 ** lgOdds））））
 Prelude> toProbabilty 2.2988530764097064 
 0.995 
  





使用对数概率





我不确定这是多么方便，或者您想要怎么处理您的概率。上面的链接提到log-odds在贝叶斯定理的情况下自然地起作用。



但我想详细说明这一点，因为 log-odds 是我通常所说的在日志空间中工作的通用技术的一个实例，当您尝试进行计算时可能会获得非常大或非常小的值，这可能非常有用。这个想法是使用对数法来转换你的计算，以减少乘法和除法和加法和减法。



我没时间了，会试着回来稍后，但要注意

pre $ 赔率成功试试=成功/（尝试 - 成功）
赔率成功​​试试= 10 **（logBase 10（成功/（尝试 - 成功）））
成功的几率try = 10 **（logBase 10成功 - logBase 10（试 - 成功）
/ pre>



如果我有更多时间希望展示概率的比率表示可用于您可能感兴趣的某些计算而不损失精度，那么我的目标就是我的目标。



结论





这个答案的一部分是我们通常不需要输入type-当我们从函数中返回 Either Foo Bar 时，我们正在做这件事。





另一个例子在图书馆我写了我最初有一个评论，用户应该只传递 Int 这是一个权力两个，否则错误。相反，我改变了功能直接采取两个幂。




I am rather new to Haskell and I was wondering how one would go about enforcing bounds using the type-system. After reading this question and checking out the linked article on smart constructors I think I get how you could generate a bounded type and generate a constructor for it like in the example:

data Probability a = P a deriving (Show, Ord, Eq)

I read in learn you a Haskell for great good, that you should

never add typeclass constraints in data declarations

so no type-constraints at this point...

instance Bounded Probability where
  minBound = P 0
  maxBound = P 1     

smartP :: (Floating a) => a -> Probability
smartP x = assert (0 <= x && x <= 1) $ P x

What I am wondering now is if and how it would be possible to do the bounds-check at compile-time for a type that is not easily represented in terms of Peano numbers (like Double...). And maybe if possible, how one would go about finding an encoding for non-enumerable but bounded types.

Furthermore: Probabilities are numbers, and I would like them to behave like numbers (have + - * etc. work on them as you would expect). Is it possible to achieve this behavior by making Probability part of the Number type-class (via deriving or some other way that doesn't involve coding all the functions by hand in the obvious way)?

Thanks a lot for any explanations.

解决方案

Interpreting your question as "What is the best way to represent probability such that invalid states are not representable", and riffing on that. I'm not an expert and don't know if this will help you.

---

Let's assume (maybe incorrectly) you are originally computing probabilities from samples. Your successes and tries are both integers in memory. Let's even assume they are arbitrary precision (in haskell Integer).

Except for the fact that they can be computed quickly, IEEE floating point is not a good way to represent probability (see here):

• they become less dense as you move from 0 to 1.0, and so if you care about precision you cannot freely transform between the probability of a thing happening and it not happening
• it's wasteful: most representable values lie outside your 0 - 1 range

From the blog post I linked above, we learn that working with odds instead of probability improves the situation (we double the number of useful values), and in particular log-odds solves the first issue above by "stretching the dense regions of floating point numbers and compressing the sparse regions."

Odds in log space

Most info related to log-odds I learned in this nice write-up byt Brian Lee and Jacob Sanders

log-odds is simply the logarithm to some base of the odds (so we use logOdds where we'd use / if we wanted probability). We can play around with it in ghci and get an intuition pretty quickly:

Prelude> let logOdds successes tries = logBase 10 ( successes / (tries - successes))
Prelude> logOdds 1 2
0.0
Prelude> logOdds 1 10
-0.9542425094393249
Prelude> logOdds 5 1000
-2.2988530764097064
Prelude> logOdds 995 1000
2.2988530764097064
Prelude> logOdds 99995 100000
4.301008280396999
Prelude> logOdds 9999995 10000000
6.3010297785166856

We can see the whole float domain is useful now, and we can convert between likelihood and unlikelihood without losing precision. There are also arguments that it's easier to make decisions based on intuition with these numbers.

So log-odds is representation isomorphic to probability where invalid states are not representable. We can convert back with

Prelude> toProbabilty lgOdds = (1 - (1 / (1 + (10**lgOdds))))
Prelude> toProbabilty 2.2988530764097064
0.995

Working with log-probability

I'm not sure how convenient this is or what you're trying to do with your probabilities. The link above mentions that log-odds works naturally in the context of Bayes theorem.

But I wanted to elaborate on this, because log-odds is an instance of a general technique I generally hear called "working in log space" which can be very helpful when trying to do calculations where you might get very large or very small values. The idea is to use the log laws to transform your calculation, to lower multiplications and divisions to additions and subtractions.

I'm out of time and will try to come back to this later, but observe

odds successes tries = successes / (tries - successes)
odds successes tries = 10 ** (logBase 10 ( successes / (tries - successes)))
odds successes tries = 10 ** (logBase 10 successes - logBase 10 (tries - successes)

my goal if I had more time being to show hopefully how a ratio representation of probability can be used for some calculations you might be interested in, without losing precision.

conclusion

Part of my point of this answer is that we don't usually need to do type-level computation to make invalid states unrepresentable. When we return Either Foo Bar from a function we're doing this.

Another example in a library I wrote I originally had a comment that the user should only pass on Int that was a power of two, otherwise error. Instead I changed the function to take the power of two directly.

这篇关于如何在编译时在haskell中进行边界检查？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！