递归Haskell的函数来确定列表元素的位置

问题描述 投票:1回答:4

我有这样的代码,将返回一个char的索引字符数组,但我希望我的功能,如果该值不是数组中返回类似-1。因为它代表的功能,如果元素不是阵列中返回该数组的大小。如何改变才能应用此功能,我的代码的任何想法?

我尽量不使用任何花哨的功能来做到这一点。我只是想不带内置的功能简单的代码。

isPartOf :: [(Char)] -> (Char) -> Int
isPartOf [] a = 0
isPartOf (a:b) c
    | a == c = 0
    | otherwise = 1 + isPartOf b c

例如:

*Main> isPartOf [('a'),('b'),('c')] ('z') 
3

但我想要:

*Main> isPartOf [('a'),('b'),('c')] ('z') 
-1
haskell recursion
4个回答
3
投票

让我们试着来定义这样的功能,但不是在元素是列表的不是一部分的情况下返回-1,我们可以返回Nothing

isPartOf :: Eq a => [a] -> a -> Maybe Int
isPartOf [] _ = Nothing
isPartOf (x : xs) a | x == a = Just 0
                     | otherwise = fmap ((+) 1) (isPartOf xs a)

因此,它的工作原理类似:

>> isPartOf [('a'),('b'),('c')] ('z')
Nothing
it :: Maybe Int

>> isPartOf [('a'),('b'),('c')] ('c')
Just 2
it :: Maybe Int

之后,我们可以使用内置函数fromMaybeNothing情况下转换为-1

>> fromMaybe (-1) $ isPartOf [('a'),('b'),('c')] ('c')
2
it :: Int

>> fromMaybe (-1) $ isPartOf [('a'),('b'),('c')] ('z')
-1
it :: Int

如果你是古玩,如果这样的功能已经存在,你可以使用Hoogle为,搜索[a] -> a -> Maybe Int功能:https://www.haskell.org/hoogle/?hoogle=%5Ba%5D+-%3E+a+-%3E+Maybe+Int

而第一个答案将是elemIndex

>> elemIndex 'c' [('a'),('b'),('c')]
Just 2
it :: Maybe Int

>> elemIndex 'z' [('a'),('b'),('c')]
Nothing
it :: Maybe Int

希望这可以帮助。


3
投票

最小的变化来实现,这是

isPartOf :: [Char] -> Char -> Int
isPartOf [] a = (-1)    -- was: 0
isPartOf (a:b) c
    | a == c = 0
    | otherwise = 1 +   -- was: isPartOf b c
          if  (isPartOf b c) < 0  then  (-2)  else  (isPartOf b c)

这是可怕的计算虽然。它重新计算两次相同的值;更糟糕的是,该计算是在递归调用完成,所以递归调用将进行两次,时间复杂度将整体从线性到指数变化!

我们不能这样做。而且,有什么特别之处Char?有很多东西特别之处Char但没有用在这里,除了比较,(==)

这可以通过比较相等的类型的值是已知的那些属于Eq(对于“平等”)型类:Eq a => aa是一种类型的可变能力任何假设任何类型的;但在这里它被限制在这样......是的,属于Eq类型的类。

因此,我们写

isPartOf :: Eq a => [a] -> a -> Int
isPartOf [] a = (-1)
isPartOf (a:b) c
    | a == c    = 0
    | otherwise = let d = isPartOf b c in
                  1 + if  d < 0  then  (-2)  else  d

(-2)看起来非常地即席!采用卫士更紧凑,更地道的版本也将让我们能够解决这个问题:

isPartOf :: Eq a => [a] -> a -> Int
isPartOf [] a = (-1)
isPartOf (a:b) c
    | a == c    = 0
    | d < 0     = d 
    | otherwise = 1 + d
          where 
          d = isPartOf b c

是的,我们可以在d子句中定义where,并在每个子句的身体使用它在我们的后卫,以及。由于懒惰它甚至不会用一次,如果并不需要它的价值,就像第一条中计算。

下面这段代码是差强人意。

有条件传递和转换是由Maybe数据类型的接口Functor /实例捕获:

fmap f Nothing  = Nothing     -- is not changed
fmap f (Just x) = Just (f x)  -- is changed

这是什么the other answer here使用。但它可以被看作是“花哨”的时候,我们才开始学习Haskell。

当你写了这样的功能,而成为“受够了”用手动重复相同的图案,并且,你会体会到它和将要使用它。但才到。

另一个值得关注的是,我们的代码计算从递归的基本情况回来的路上它的结果。

但是它可以代替计算它on the way forward,朝它,因此它可以立即返回它当匹配字符被找到。如果列表的末尾被发现,丢弃到目前为止的结果计算,并返回(-1)代替。这是the second answer采取的做法。

虽然创建一个附加功能的乱丢全局命名空间。它通常由内部定义它,在所谓的“工人/包装”改造要做到这一点:

isPartOf :: Eq a => [a] -> a -> Int
isPartOf xs c = go xs 0
   where
   go [] i = (-1)
   go (a:b) i
    | a == c    = i
    | otherwise = -- go b (1 + i)
                  go b $! (1 + i)

另外的福音是,我们并不需要绕过不变值c - 这是在外部范围内都有效,从内部的“工人”功能go点,“包装”的,只有进入到我们的函数,isPartOf

$!是一个特殊的电话运营商确保其参数值计算向右走,而不会延迟。这消除了不希望的(在这种情况下)的懒惰和甚至更提高了编码效率。

不过从外观设计上,最好是改为返回使用“特殊”的值,它是不那么特殊毕竟裹着i指数Maybe(即Just iNothing)的整体环境清洁点 - 它仍然是一个Int

这是好事,有类型反映了我们的意图,并表示Maybe Int清楚,干净,所以我们不必记住哪一个数值是特殊的,其定期,这样的知识是不是外部对我们的程序文本,但固有的给它。

这是一个小而简单的变化,最好的部分,从前面的两个变种结合:

isPartOf :: Eq a => [a] -> a -> Maybe Int
isPartOf .....
  .......
  .......  Nothing .....
  .......
  .......  Just i  .....
  .......

(无代码的测试。如果有错误,我们诚邀您找到他们,并予以纠正,并通过试验验证它)。


2
投票

您可以轻松地实现它,如果你只是通过当前元素IDX下一个递归:

isPartOf :: [Char] -> Char -> Int
isPartOf lst c = isPartOf' lst c 0

isPartOf' :: [Char] -> Char -> Int -> Int
isPartOf' [] a _ = -1
isPartOf' (a:b) c idx
    | a == c = idx
    | otherwise = isPartOf' b c (idx + 1)

0
投票

您正在使用您的函数作为累加器。这除了与负一层的补充清凉。一种储存器,无法从积累到从功能蓄电池提供负1。你想两回事切换。您可以使用一个计数器的一两件事,然后,如果因为未找到匹配和负1发出,并没有什么损失的数量变得不必要。计数是另一个参数。啊。你也许可以使用但复杂。两种功能,像上面更简单。这里有两个功能。第一个是你的,但累加器不是加它的拼接。

cIn (x:xs) c | x == c    =  [1]
             | null xs   = [-1]
             | otherwise = 1:cIn xs c


Cin ['a','b','c'] 'c'

[1,1,1]

cIn ['a','b','c'] 'x'

[1,1,-1]

所以第二个功能是

f ls = if last ls == 1 then sum ls else -1 

它会

f $ Cin ['a','b','c'] 'c'

3

f $ Cin ['a','b','c'] 'x'

-1

你可以通过改变[1][0]零的指数基

© www.soinside.com 2019 - 2024. All rights reserved.