在围绕1:20标记的讨论中,Edward Kmett提到Haskell缺乏"类型回溯".考虑在列表上实现的"集合相等"(其中顺序和多重性被忽略)的问题:
equals :: [a] -> [a] -> Bool
根据类型类的性质,我不能提供低效的O(n²)比较,如果我们只有,Eq a但如果有的话,有效地比较O(n log n)中的列表Ord a.
我确实理解为什么这样的设施会有问题.与此同时,爱德华说,有一些"你可以玩的技巧",例如提到类型家庭.
因此我的问题是,实现相同效果的解决方法是什么:
此解决方法不一定需要使用类型类.
编辑:一些人认为简单地提供equals和efficientEquals为两个不同的方法.总的来说,我同意这是更多Haskell惯用法.但是,我不相信这总是可行的.例如,如果上面的equals方法本身是类型类的一部分,那该怎么办:
class SetLike s where
equals :: Eq a => s a -> s a -> Bool
假设此类已由其他人提供,因此我不能简单地向类型类添加新函数.我现在想要定义实例[].我知道无论有什么约束,都[]可以提供实现,但如果有更多信息可用,我无法告诉我的实例使用更高效的版本.equalsaa
也许我可以将列表包装在一个新类型中并用一些额外的类型信息标记它？
考虑以下运行GROUP BY具有相对大量聚合和相对大量组的a的示例:
import org.apache.spark.sql.hive.HiveContext
import org.apache.spark.SparkContext._
val h = new HiveContext(sc)
import h.implicits._
val num_columns = 3e3.toInt
val num_rows = 1e6.toInt
val num_groups = 1e5.toInt
case class Data(A: Long = (math.random*num_groups).toLong)
val table = (1 to num_rows).map(i => Data()).toDF
val aggregations = (1 to num_columns).map(i => s"count(1) as agg_$i")
table.registerTempTable("table")
val result = h.sql(s"select a, ${aggregations.mkString(",")} from table group by a")
// Write the result to make sure everyting is executed
result.save(s"result_${num_columns}_${num_rows}_${num_groups}.parquet", "parquet")
这个作业的输入只有8MB,输出大约2.4GB,我在一个集群上运行它,每个工作机器有61GB内存.结果:所有工作程序都因OutOfMemory异常而崩溃.num_columns由于GC开销,即使工作值较低也会变得非常慢.
我们尝试的事情包括:
我在使用GHC.TypeLits时遇到了问题.考虑以下GADT:
data Foo :: Nat -> * where
SmallFoo :: (n <= 2) => Foo n
BigFoo :: (3 <= n) => Foo n
我的理解是,现在每个n类型Foo n都只填充一个值(根据值的值,可以是SmallFoo或BigFoo n).
但是,如果我现在想构建一个具体的实例,如下所示:
myFoo :: Foo 4
myFoo = BigFoo
然后GHC(7.6.2)吐出以下错误消息:
No instance for (3 <= 4) arising from a use of `BigFoo'
Possible fix: add an instance declaration for (3 <= 4)
In the expression: BigFoo
In an equation for `myFoo': myFoo = BigFoo
这看起来很奇怪 - 我预计会有这种类型级别nat比较的预定义实例.如何使用类型级自然在我的数据构造函数中表达这些类型的约束？
假设我有一个适用的数据类型A.(为了这个例子,我们可以假设A是Identity).
我现在有一个新的数据类型,对应于从一个A到另一个的"转换" :
data B a b = B (A a -> A b)
我想定义一个普通的Applicative实例,(B a)它产生一个新的转换,它将两个参数应用于<*>它的输入,然后使用来自A的Applicative实例的<*>的定义.
制定这个很简单:
instance Applicative (B a) where
pure x = B $ const $ pure x
(B ftrans) <*> (B xtrans) = B fxtrans
where fxtrans inp = let fout = ftrans inp
xout = xtrans inp
in fout <*> xout
但是,我觉得应该有一种直截了当的无意义的方式来编写这个使用(-> a)Applicative Functor 的事实.
作为我的想法的一个例子,考虑我对相应的Functor实例的定义:
instance Functor (B a) where …假设我有一个班级'小工具'.在我的应用程序中,我创建了许多小部件(用于缓存局部性和其他原因)我保存在向量中.
为了有效查找,我想实现一个索引数据结构.为了这个问题,让我们假设它是一个简单的查找表,从int索引到上述向量中的Widget元素.我的问题是:查找表的内容应该是什么.换句话说,我应该用哪种类型替换问号
using LookupTable = std::vector<?>
我看到以下选项:
在这些选项中,索引似乎是不会被向量调整大小无效的唯一选项.我可能实际上可以避免调整大小,但是,实现查找表就像这意味着对矢量实现进行假设,从"解耦设计"的角度来看这似乎是不合理的.
OTOH索引不是类型安全的:如果我从查找表中得到的东西是引用,我只能使用它来访问相应的小部件.使用size_t值我可以进行无意义的操作,例如将结果乘以3.还要考虑以下两个签名:
void doSomethingWithLookupResult(Widget& lookupResult);
void doSomethingWithLookupResult(size_t lookupResult);
前者更具描述性.
总结:我可以将哪种数据类型用于查找表,以实现与向量实现和类型安全性的分离？
假设一个SchemaRDD rdd,注册表格customer.您想根据用户输入过滤掉记录.您可能有如何做到这一点的一个想法如下:
rdd.sqlContext.sql(s"SELECT * FROM customer WHERE name='$userInput'")
然而,自PHP的旧时代以来,我们知道这会导致令人讨厌的事情.是否有相当于PreparedStatement？我能找到的唯一与远程相关的东西是org.apache.commons.lang.StringEscapeUtils.escapeSql.